Article

Proving Integrality Gaps without Knowing the Linear Program

Authors:

Sanjeev Arora,

Béla Bollobás,

László LovászAuthors Info & Claims

FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science

Pages 313 - 322

Published: 16 November 2002 Publication History

Publisher Site

Abstract

Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an integrality gap of 2 - o(1) for three families of linear relaxations for vertex cover, and our methods seem relevant to other problems as well.

Cited By

View all

Ghosh MTulsiani M(2017)From weak to strong LP gaps for all CSPsProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135606(1-27)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135606
Kenkre SPandit VPurohit MSaket R(2017)On the Approximability of Digraph OrderingAlgorithmica10.1007/s00453-016-0227-778:4(1182-1205)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00453-016-0227-7
Chan SLee JRaghavendra PSteurer D(2016)Approximate Constraint Satisfaction Requires Large LP RelaxationsJournal of the ACM10.1145/281125563:4(1-22)Online publication date: 26-Oct-2016
https://dl.acm.org/doi/10.1145/2811255
Show More Cited By

Recommendations

Integrality gaps for strong linear programming and semidefinite programming relaxations
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

The Densest k-subgraph problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for Densest k-subgraph: the current ...
Integrality gaps for strengthened linear relaxations of capacitated facility location

Metric uncapacitated facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. Capacitated facility location (Cfl) is a generalization for which there are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science

November 2002

569 pages

ISBN:0769518222

Publisher

IEEE Computer Society

United States

Publication History

Published: 16 November 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ghosh MTulsiani M(2017)From weak to strong LP gaps for all CSPsProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135606(1-27)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135606
Kenkre SPandit VPurohit MSaket R(2017)On the Approximability of Digraph OrderingAlgorithmica10.1007/s00453-016-0227-778:4(1182-1205)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00453-016-0227-7
Chan SLee JRaghavendra PSteurer D(2016)Approximate Constraint Satisfaction Requires Large LP RelaxationsJournal of the ACM10.1145/281125563:4(1-22)Online publication date: 26-Oct-2016
https://dl.acm.org/doi/10.1145/2811255
Kolliopoulos SMoysoglou Y(2016)Integrality gaps for strengthened linear relaxations of capacitated facility locationMathematical Programming: Series A and B10.1007/s10107-015-0916-z158:1-2(99-141)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10107-015-0916-z
Fiorini SMassar SPokutta STiwary Hde Wolf R(2015)Exponential Lower Bounds for Polytopes in Combinatorial OptimizationJournal of the ACM10.1145/271630762:2(1-23)Online publication date: 6-May-2015
https://dl.acm.org/doi/10.1145/2716307
Kauers MO'Donnell RTan LZhou YChekuri C(2014)Hypercontractive inequalities via SOS, and the Frankl-Rödl graphProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634193(1644-1658)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634193
Braverman MMoitra ABoneh DRoughgarden TFeigenbaum J(2013)An information complexity approach to extended formulationsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488629(161-170)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488629
Park MHong S(2013)Handelman rank of zero-diagonal quadratic programs over a hypercube and its applicationsJournal of Global Optimization10.1007/s10898-012-9906-356:2(727-736)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s10898-012-9906-3
Fiorini SMassar SPokutta STiwary Hde Wolf RKarloff HPitassi T(2012)Linear vs. semidefinite extended formulationsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2213988(95-106)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2213988
Chan YLau L(2012)On linear and semidefinite programming relaxations for hypergraph matchingMathematical Programming: Series A and B10.1007/s10107-011-0451-5135:1-2(123-148)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1007/s10107-011-0451-5
Show More Cited By

Abstract

Cited By

Recommendations

Integrality gaps for strong linear programming and semidefinite programming relaxations

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

Integrality gaps for strengthened linear relaxations of capacitated facility location

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations