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"”.
-
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 …
-
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 …
-
ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ Η ΕΦΑΡΜΟΓΗ ΤΟΥΣ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ
… 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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …