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

linear programmingapproximation algorithmsinapproximabilityvertex coverNP-hard problemsintegrality gapslift-and-project

Mathematics Subject Classification ID

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

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

(31)

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

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)