Proving integrality gaps without knowing the linear program

DOI10.4086/TOC.2006.V002A002MaRDI QIDQ3002764zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Iannis Tourlakis, Sanjeev Arora, László Lovász

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2006.v002a002

zbMATH Keywords

approximation algorithmsinapproximabilityintegrality gapslift-and-projectlinear programmingNP-hard problemsvertex cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Integrality gap of the vertex cover linear programming relaxation
• Integrality gaps for Sherali-Adams relaxations
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cited in

(32)

• Priority algorithms for graph optimization problems
• The strength of Dantzig-Wolfe reformulations for the stable set and related problems
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Integrality gap of the vertex cover linear programming relaxation
• Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications
• Integrality gaps for colorful matchings
• Convex relaxations and integrality gaps
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Separation between estimation and approximation
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Testing additive integrality gaps
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
• Toward a model for backtracking and dynamic programming
• A note on the integrality gap of an ILP formulation for the periodic maintenance problem
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Superlinear Integrality Gaps for the Minimum Majority Problem
• Sherali-adams strikes back
• Sherali-Adams strikes back
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Testing additive integrality gaps
• A stronger model of dynamic programming algorithms
• Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
• Expanders with respect to Hadamard spaces and random graphs
• Approximate graph colouring and the hollow shadow
• Approximate graph coloring and the crystal with a hollow shadow
• Semidefinite programming and linear equations vs. homomorphism problems
• Density Frankl-Rödl on the sphere
• Strong and weak edges of a graph and linkages with the vertex cover problem

This page was built for publication: Proving integrality gaps without knowing the linear program

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002764)