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"”.

  1. 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 …

    toronto-retro Repository record for Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations (opens in a new tab)

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

    cornell Repository record for Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps (opens in a new tab)

  3. 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 …

    lethbridge Repository record for Approximation algorithms for a graph-cut problem with applications to a clustering problem in bioinformatics (opens in a new tab)

  4. 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 …

    rice Repository record for Stochastic Assignment with Expiration (opens in a new tab)

  5. 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 …

    toronto-retro Repository record for On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems (opens in a new tab)

  6. 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 …

    cornell Repository record for Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations (opens in a new tab)

  7. 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 …

    maryland Repository record for Algorithms and Generalizations for the Lovasz Local Lemma (opens in a new tab)

  8. 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. …

    ottawa-retro Repository record for Approximation Algorithms for Network Connectivity Problems (opens in a new tab)

  9. 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 …

    ottawa-retro Repository record for The integrality gap of the asymmetric travelling salesman problem (opens in a new tab)

  10. 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 …

    gatech Repository record for Intractability results for problems in computational learning and approximation (opens in a new tab)

  11. 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 …

    uiuc Repository record for Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts (opens in a new tab)