Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 40 for “"Max-Cut"”.

  1. On Graph Coloring, Max Cut, and Semidefinite Rank

    … NP-complete problems, graph coloring and max cut, both of which have established semidefinite programming relaxations. We introduce the use of semidefinite programming complementary slackness conditions to understand when an optimal solution to one of these SDP relaxations can be …

    cornell Repository record for On Graph Coloring, Max Cut, and Semidefinite Rank (opens in a new tab)

  2. Improving the smoothed complexity of flip for max cut problems

    Finding locally optimal solutions for max-cut and max-k-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical …

    uiuc Repository record for Improving the smoothed complexity of flip for max cut problems (opens in a new tab)

  3. On the Study of Fitness Landscapes and the Max-Cut Problem

    … the complexity of NP-Hard problems, using the Max-Cut and the Max-k-Cut problems, and the study of fitness landscapes. The Max-Cut and Max-k-Cut problems are well studied NP-hard problems specially since the approximation algorithm of Goemans and Williamson (1995) which introduced the use of …

    qucosa-diss

  4. Inverted Sequence Identification in Diploid Genomic Scaffold Assembly via Weighted MAX-CUT Reduction

    … and show that it is equivalent to the weighted MAX-CUT problem. We present a greedy heuristic solution which we comparatively assess with other solutions to the contig orientation problem, including an advanced MAX-CUT heuristic. We illustrate how a solution to this problem provides a simple …

    byu Repository record for Inverted Sequence Identification in Diploid Genomic Scaffold Assembly via Weighted MAX-CUT Reduction (opens in a new tab) Download PDF for Inverted Sequence Identification in Diploid Genomic Scaffold Assembly via Weighted MAX-CUT Reduction (opens in a new tab)

  5. Max-Cut QAOA Cost Hamiltonian Compilation for Unweighted Graphs Using Minimum Global Controls and Qubit Bit Flips

    … quantum-classical algorithm, QAOA, for the max-cut problem on trapped-ion quantum computers. As opposed to the standard $CNOT$ and $R_z$ gate compilation of the cost Hamiltonian for QAOA, here the goal is to compile it to global coupling operations and individual qubit bit flips. Rajakumar …

    rice Repository record for Max-Cut QAOA Cost Hamiltonian Compilation for Unweighted Graphs Using Minimum Global Controls and Qubit Bit Flips (opens in a new tab)

  6. Classical Optimization to Improve Variational Quantum Algorithms

    … to develop fast hybrid QAOA solvers for the Max-Cut problem. First, we study graph instances that are "challenging" to solve classically, to better understand where quantum algorithms might have an advantage over classical methods. Next, we introduce the notion of "warm-starting" in quantum …

    gatech Repository record for Classical Optimization to Improve Variational Quantum Algorithms (opens in a new tab)

  7. Exploring Reconfigurable Analog Hopfield and Ising Networks on the SoC FPAA

    … efficiently solved three NP-hard problems (max-cut, 3SAT, and TSP), converging to optimal or good solutions in microseconds. An Ising network is also built on the same FPAA and compared to the Hopfield network on solving small max-cut and associative memory problems. The analog Hopfield …

    gatech Repository record for Exploring Reconfigurable Analog Hopfield and Ising Networks on the SoC FPAA (opens in a new tab)

  8. Knowledge-based learning for classification of hyperspectral data

    … no labeled samples are available. An integrated max-cut hierarchical decomposition algorithm that uses support vector machines to classify multi-class land cover data is proposed to address the high dimensional input problem. The hierarchical support vector machine (HSVM) classifier solves a …

    texas Repository record for Knowledge-based learning for classification of hyperspectral data (opens in a new tab)

  9. New Convex Relaxations for the Maximum Cut and VLSI Layout Problems

    … for two such hard problems, namely the Maximum-Cut (Max-Cut) problem and the VLSI (Very Large Scale Integration of electronic circuits) layout problem. We derive and study the properties of two new strengthened semidefinite programming relaxations for the Max-Cut problem. Our theoretical …

    waterloo Repository record for New Convex Relaxations for the Maximum Cut and VLSI Layout Problems (opens in a new tab)

  10. Classical Shadows para algoritmos quânticos de feedback

    … (KET), para a resolução do problema do Max-Cut e implementamos CS na rotina de feedback para estimar os valores esperados, comparando essa abordagem com medições diretas. Os ensaios numéricos mostram que, dependendo da geometria do grafo no problema de Max-Cut, o número de medições …

    brazil-ufsc Repository record for Classical Shadows para algoritmos quânticos de feedback (opens in a new tab)

  11. Physical Design for Multichip Modules

    … and layer assignment. The emphasis is on maximizing the electrical performance, based on accurate modeling of MCM interconnect behavior. A new approach, called Reciprocal Expansion, is developed for rapidly estimating the time-domain response of lossy coupled MCM interconnect structures, …

    uiuc Repository record for Physical Design for Multichip Modules (opens in a new tab)

  12. Judicious partitions of graphs and hypergraphs

    Classical partitioning problems, like the Max-Cut problem, ask for partitions that optimize one quantity, which are important to such fields as VLSI design, combinatorial optimization, and computer science. Judicious partitioning problems on graphs or hypergraphs ask for partitions that optimize …

    gatech Repository record for Judicious partitions of graphs and hypergraphs (opens in a new tab)

  13. Four Problems in Probability and Optimization

    … we consider the $K_i$-cover problem and the max cut problem. We show that a family of facets arising from $K_i$-$p$-holes is valid on the $i/2$ theta body. We also prove an integrality gap of $1/2$ for the triangle free problem, and show that at least $n/2$ steps are required for the triangle …

    washington Repository record for Four Problems in Probability and Optimization (opens in a new tab)

  14. Parameter setting strategies in multi-angle quantum approximate optimization algorithm

    Combinatorial optimization problems such as Max-Cut are difficult to solve exactly on classical computers, and variational quantum algorithms like Quantum Approximate Optimization Algorithm (QAOA) offer a promising avenue to solve these problems on near-term quantum computers. The QAOA prepares a …

    chalmers Repository record for Parameter setting strategies in multi-angle quantum approximate optimization algorithm (opens in a new tab)

  15. Approximation and Optimization Approaches for Graph Cuts, Experimental Design, and Routing Problems

    This dissertation explores three topics: maximum graph cuts, the design of experiments, and the traveling salesman problem. First, we study MAX-3-SECTION, where the goal is to partition a weighted graph into three equally sized parts to maximize the weight of crossing edges. We present a new …

    gatech Repository record for Approximation and Optimization Approaches for Graph Cuts, Experimental Design, and Routing Problems (opens in a new tab)

  16. Metaheurísticas aplicadas al problema de compilación de circuitos cuánticos

    … Algorithm (QAOA) para resolver problemas Max-Cut. En la literatura, este problema se ha modelado tanto en forma de planning como de scheduling con minimización del makespan. Algunos de los métodos presentes en la literatura proponen la utilización de metaheurísticas como algoritmos …

    oviedo Repository record for Metaheurísticas aplicadas al problema de compilación de circuitos cuánticos (opens in a new tab)

  17. ISING MACHINE IMPLEMENTATION USING CROSS-COUPLED OSCILLATORS

    … function are studied when solving different Max-Cut problems. By altering the synchronization to interaction coupling strength ratio, around 99% optimal probability is achieved. Demonstrating this prototype hardware oscillator-based Ising machine is capable of solving different CO problems.

    nus Repository record for ISING MACHINE IMPLEMENTATION USING CROSS-COUPLED OSCILLATORS (opens in a new tab) Download file for ISING MACHINE IMPLEMENTATION USING CROSS-COUPLED OSCILLATORS (opens in a new tab)

  18. Optimization in Geometric Graphs: Complexity and Approximation

    … areas, we study several problems including maximum independent set, minimum vertex coloring, minimum clique partition, max-cut and min-bisection. Although these problems have been widely studied in the context of unit disk graphs, which are the two dimensional version of unit ball graphs, …

    tamu Repository record for Optimization in Geometric Graphs: Complexity and Approximation (opens in a new tab)

  19. A Quantum Genetic Algorithm Framework For The MaxCut Problem

    The MaxCut problem is a fundamental problem in Combinatorial Optimization, with sig- nificant implications across diverse domains such as logistics, network design, and statistical physics. The algorithm represents innovative approaches that balance theoretical rigor with practical scalability. The …

    brazil-ufpe Repository record for A Quantum Genetic Algorithm Framework For The MaxCut Problem (opens in a new tab)

Page 1 of 2