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 “"Integrality gaps"”.
-
Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations
… related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build …
-
Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps
… analysis of this linear program's \emph{integrality gap} (which dictates its use in proving approximation guarantees) has not been improved in nearly 40 years of active research. This thesis contributes to two main avenues of TSP research towards breaking these bottlenecks, both of which …
-
Approximation algorithms for a graph-cut problem with applications to a clustering problem in bioinformatics
… programming formulations and exhibit large integrality gaps for various formulations. This is indicative of the difficulty in obtaining constant factor approximation algorithms using the primal-dual schema. We propose three approximation algorithms for the problem. We evaluate the algorithms …
-
Stochastic Assignment with Expiration
… of our LP-based analysis by providing tight integrality gaps as well as worst-case instances. Returning to the capacitated problem, we provide another LP relaxation. We generalize our previous algorithms to evaluate their numerical performance on the harder, capacitated problem. We observe …
-
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
… There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations. In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The …
-
Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations
… unit-weight graphical metric s-t path TSP. The integrality gaps of the LP relaxations for all three problems are studied. Then we consider the bottleneck asymmetric TSP, where the objective is minimizing the bottleneck (or maximum-length) edge cost rather than the total edge cost. We present the …
-
Algorithms and Generalizations for the Lovasz Local Lemma
… set-cover. We also give hardness reductions and integrality gaps, showing that our partial resampling based algorithm obtains nearly optimal approximation factors. We give a variant of the Moser-Tardos algorithm for random permutations, one of the few cases of the LLL not covered by the original …
-
Approximation Algorithms for Network Connectivity Problems
… and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. …
-
The integrality gap of the asymmetric travelling salesman problem
… costs are metric. In this thesis we study the integrality gap for the ATSP, i.e. the worst-case ratio between the ATSP and its linear programming relaxation ATSPLP. The ATSPLP provides a lower bound for the ATSP, which is useful for branch and bound solution techniques as well as for providing …
-
Intractability results for problems in computational learning and approximation
… as Maximum Cut and Sparsest Cut by constructing integrality gap examples for them. For Maximum Cut and Sparsest Cut we construct examples -- with gaps alpha[superscript{-1}] - ε (alpha is the Goemans-Williamson constant) and Omega((logloglog n)[superscript{1/13}]) respectively -- for the standard …
-
A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization
… in our analysis can be applied to obtain the integrality gaps of convex relaxations.
-
Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts
… on the Hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN(\Z_2). We conjecture that augmenting the SDP with triangle inequalities makes the SDP exact upto constants on the Hypercube. We further …