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 12 of 12 for “"MAX CUT PROBLEM"”.

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

    … thesis is to study 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 …

    qucosa-diss

  2. 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)

  3. ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ Η ΕΦΑΡΜΟΓΗ ΤΟΥΣ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ

    … ALGORITHMS AND THEIR APPLICATION TO GRAPH PROBLEMS. MORE PRECISELY: 1. WE PRESENT A DETERMINISTIC TECHNIQUE BASED ON THE DECOMPOSITION OF A PLANAR DIGRAPH INTO SPECIAL OUTERPLANAR SUBGRAPHS CALLED HAMMOCKS. 2. WE PRESENT A PROBABILISTIC TECHNIQUE FOR FINDING PARALLEL APPROXIMATION SOLUTIONS …

    greece Repository record for ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ Η ΕΦΑΡΜΟΓΗ ΤΟΥΣ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ (opens in a new tab)

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

    It is well known that many of the optimization problems which arise in applications are <I>hard</I>, which usually means that they are NP-hard. Hence much research has been devoted to finding <I>good</I> relaxations for these hard problems. Usually a <I>good</I> relaxation is one which can be …

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

  5. APPLICATIONS OF GAUSSIAN FIELDS TO THE PERMANENT AND THE MATCHING POLYNOMIAL

    … explore applications of Gaussian fields to the problems of approximating the permanent of a matrix and to the theory of the matching polynomial of a graph. In the first part of this thesis, we introduce a new randomized algorithm that leverages a form of Wick's theorem to estimate the permanent …

    temple Repository record for APPLICATIONS OF GAUSSIAN FIELDS TO THE PERMANENT AND THE MATCHING POLYNOMIAL (opens in a new tab)

  6. Preserving large cuts in fully dynamic graphs

    This thesis initiates the study of the MAX-CUT problem in fully dynamic graphs. Given a graph $G=(V,E)$, we present the first fully dynamic algorithms to maintain a $\frac{1}{2}$-approximate cut in sublinear update time under edge insertions and deletions to $G$. Our results include the following …

    uvic Repository record for Preserving large cuts in fully dynamic graphs (opens in a new tab)

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

    … is what is termed the contig orientation problem. We define this problem using bidirected graph theory 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 …

    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)

  8. Four Problems in Probability and Optimization

    This thesis studies bootstrap percolation, a problem in probability, as well as several topics in the application of sums of squares to combinatorial optimization. In the chapter on percolation, we bound the critical probability for bootstrap percolation on the Hamming torus, as well as the …

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

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

    We study an operation compilation problem, associated with the hybrid 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 …

    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)

  10. Classical Optimization to Improve Variational Quantum Algorithms

    … quantum technology to solve challenging problems in combinatorial optimization. Recently, in 2014, Farhi et. al proposed a general Quantum Approximate Optimization Algorithm (QAOA) to obtain solutions to NP-hard problems, and showed that this algorithm converges to the optimal solutions …

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

  11. Optimization in Geometric Graphs: Complexity and Approximation

    We consider several related problems arising in geometric graphs. In particular, we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact and approximate solutions. In addition, we establish …

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

  12. 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)