interview

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Authors:

Samuel Fiorini,

Sebastian Pokutta,

Hans Raj Tiwary,

Ronald de WolfAuthors Info & Claims

Journal of the ACM (JACM), Volume 62, Issue 2

Article No.: 17, Pages 1 - 23

https://doi.org/10.1145/2716307

Published: 06 May 2015 Publication History

Abstract

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

Supplementary Material

Auxiliary material (auxiliary.html)

Note about the resolution of an open question in Section 5 (unrefereed material)

Download
.73 KB

References

[1]

S. Aaronson. 2006. Lower bounds for local search by quantum arguments. SIAM J. Comput. 35, 4, 804--824. (Earlier version in STOC'04).

Digital Library

[2]

D. Aharonov and O. Regev. 2004. Lattice problems in NP ∩ coNP. In Proceedings of FOCS 2004. 362--371.

Digital Library

[3]

S. Arora, B. Bollobás, and L. Lovász. 2002. Proving integrality gaps without knowing the linear program. In Proceedings of FOCS 2002. 313--322.

Digital Library

[4]

S. Arora, B. Bollobás, L. Lovász, and I. Tourlakis. 2006. Proving integrality gaps without knowing the linear program. Theory Comput. 2, 19--51.

[5]

D. Avis and H. R. Tiwary. 2013. On the Extension Complexity of Combinatorial Polytopes. In Proceedings of ICALP(1) 2013. 57--68.

Digital Library

[6]

E. Balas. 1985. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algeb. Disc. Meth. 6, 466--486.

Digital Library

[7]

E. Balas, S. Ceria, and G. Cornuéjols. 1993. A lift-and-project algorithm for mixed 0-1 programs. Math. Prog. 58, 295--324.

Digital Library

[8]

S. Benabbas and A. Magen. 2010. Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain. In Proceedings of IPCO 2010. 299--312.

Digital Library

[9]

G. Braun, S. Fiorini, S. Pokutta, and D. Steurer. 2012. Approximation limits of linear programs (beyond hierarchies). In Proceedings of FOCS 2012. 480--489.

Digital Library

[10]

G. Braun, S. Fiorini, and S. Pokutta. 2013a. Average case polyhedral complexity of the maximum stable set problem. arXiv:1311.4001.

[11]

G. Braun, R. Jain, T. Lee, and S. Pokutta. 2013b. Information-theoretic approximations of the nonnegative rank. ECCC Report no. 158 (2013).

[12]

G. Braun and S. Pokutta. 2013. Common information and unique disjointness. In Proceedings of FOCS 2013. 688--697.

Digital Library

[13]

M. Braverman and A. Moitra. 2013. An information complexity approach to extended formulations. In Proceedings of STOC 2013. 161--170.

Digital Library

[14]

J. Briët, D. Dadush, and S. Pokutta. 2013. On the existence of 0/1 polytopes with high semidefinite extension complexity. In Algorithms ESA 2013, Lecture Notes in Computer Science, vol. 8125, Springer, 217--228.

[15]

H. Buhrman, R. Cleve, S. Massar, and R. de Wolf. 2010. Nonlocality and communication complexity. Rev. Modern Phys. 82, 665.

[16]

J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi. 2006. Rank bounds and integrality gaps for cutting planes procedures. Theory Comput. 2, 65--90.

[17]

S. O. Chan, J. R. Lee, P. Raghavendra, and D. Steurer. 2013. Approximate Constraint Satisfaction Requires Large LP Relaxations. In Proceedings of FOCS 2013, 350--359.

Digital Library

[18]

M. Charikar, K. Makarychev, and Y. Makarychev. 2009. Integrality gaps for Sherali-Adams relaxations. In Proceedings of STOC 2009. 283--292.

Digital Library

[19]

M. Conforti, G. Cornuéjols, and G. Zambelli. 2010. Extended formulations in combinatorial optimization. 4OR 8, 1--48.

[20]

G. B. Dantzig. 1951. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, John Wiley & Sons Inc., New York, 339--347.

[21]

C. De Simone. 1990. The cut polytope and the Boolean quadric polytope. Disc. Math. 79, 71--75.

Digital Library

[22]

M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Algorithms and Combinatorics Series, vol. 15, Springer-Verlag.

Digital Library

[23]

A. Drucker and R. de Wolf. 2011. Quantum proofs for classical theorems. Theory Comput. Graduate Surveys 2.

[24]

Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary. 2011. Extended formulations, non-negative factorizations and randomized communication protocols. arXiv:1105.4127.

[25]

H. Fawzi and P. A. Parrilo. 2013. Exponential lower bounds on fixed-size PSD rank and semidefinite extension complexity. arXiv:1311.2571.

[26]

W. Fernandez de la Vega and C. Mathieu. 2007. Linear programming relaxation of Maxcut. In Proceedings of SODA 2007. 53--61.

Digital Library

[27]

S. Fiorini, V. Kaibel, K. Pashkovich, and D. O. Theis. 2011. Combinatorial bounds on nonnegative rank and extended formulations. arXiv:1111.0444.

[28]

S. Fiorini, S. Massar, M. K. Patra, and H. R. Tiwary. 2013. Generalised probabilistic theories and conic extensions of polytopes. CoRR abs/1310.4125.

[29]

K. Georgiou, A. Magen, T. Pitassi, and I. Tourlakis. 2010. Integrality gaps of 2&mins;o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy. SIAM J. Comput. 39, 3553--3570.

Digital Library

[30]

K. Georgiou, A. Magen, and M. Tulsiani. 2009. Optimal Sherali-Adams gaps from pairwise independence. In Proceedings of APPROX-RANDOM 2009. 125--139.

Digital Library

[31]

M. X. Goemans and D. P. Williamson. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115--1145.

Digital Library

[32]

J. Gouveia, P. A. Parrilo, and R. R. Thomas. 2010. Theta bodies for polynomial ideals. SIAM J. Optim. 20, 2097--2118.

Digital Library

[33]

J. Gouveia, P. A. Parrilo, and R. R. Thomas. 2013. Lifts of convex sets and cone factorizations. Math. Oper. Res.38, 2, 248--264.

Digital Library

[34]

J. Håstad. 1999. Clique is Hard to Approximate within n^1&mins;ε. Acta Math. 182, 105--142. (Earlier version in Proceedings of FOCS 1996.)

[35]

H. Huang and B. Sudakov. 2012. A counterexample to the Alon-Saks-Seymour conjecture and related problems. Combinatorica32, 2, 205--219.

Digital Library

[36]

R. Jain, Y. Shi, Z. Wei, and S. Zhang. 2013. Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Trans. Inf. Theory59, 8, 5171--5178.

Digital Library

[37]

V. Kaibel. 2011. Extended formulations in combinatorial optimization. Optima 85, 2--7.

[38]

V. Kaibel, K. Pashkovich, and D. O. Theis. 2010. Symmetry matters for the sizes of extended formulations. In Proceedings of IPCO 2010. 135--148.

Digital Library

[39]

V. Kaibel and S. Weltge. 2013. A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete Computa. Geom. 53, 2, 396--401.

Digital Library

[40]

N. Karmarkar. 1984. A new polynomial time algorithm for linear programming. Combinatorica 4, 373--395.

Digital Library

[41]

I. Kerenidis and R. de Wolf. 2004. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. 69, 3, 395--420. (Earlier version in STOC 2003).

Digital Library

[42]

L. G. Khachiyan. 1979. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR244, 5, 1093--1096.

[43]

S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. 2007. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs&quest; SIAM J. Comput.37, 1, 319--357.

Digital Library

[44]

H. Klauck, T. Lee, and S. Zhang. 2011. An explicit and exponential separation between randomized and quantum correlation complexities. Unpublished manuscript from Oct/Nov 2011. Personal communication between Troy Lee and Ronald de Wolf, December 2011 at Centre for Quantum Technologies, Singapore.

[45]

E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press.

Digital Library

[46]

E. Kushilevitz and E. Weinreb. 2009a. The communication complexity of set-disjointness with small sets and 0-1 intersection. In Proceedings of FOCS 2009. 63--72.

Digital Library

[47]

E. Kushilevitz and E. Weinreb. 2009b. On the complexity of communication complexity. In Proceedings of STOC 2009. 465--474.

Digital Library

[48]

J. R. Lee, P. Raghavendra, and D. Steurer. 2015. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of STOC 2015.

[49]

T. Lee and D. O. Theis. 2012. Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix. arXiv:1203.3961.

[50]

L. Lovász. 1979. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1--7.

Digital Library

[51]

L. Lovász. 2003. Semidefinite programs and combinatorial optimization. In Recent Advances in Algorithms and Combinatorics. CMS Books Math./Ouvrages Math, SMC Series, vol. 11, Springer, 137--194.

[52]

L. Lovász and M. Saks. 1993. Communication complexity and combinatorial lattice theory. J. Comput. Syst. Sci. 47, 322--349.

Digital Library

[53]

L. Lovász and A. Schrijver. 1991. Cones of matrices and set-functions and 0&mins;1 optimization. SIAM J. Optim. 1, 166--190.

Digital Library

[54]

N. D. Mermin. 2007. Quantum Computer Science: An Introduction. Cambridge University Press.

Digital Library

[55]

M. A. Nielsen and I. L. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press.

Digital Library

[56]

K. Pashkovich. 2009. Symmetry in extended formulations of the permutahedron. arXiv:0912.3446.

[57]

S. Pokutta and M. Van Vyve. 2013. A note on the extension complexity of the knapsack polytope. Oper. Res. Lett.41, 4, 347--350.

[58]

A. A. Razborov. 1992. On the distributional complexity of disjointness. Theoret. Comput. Sci.106, 2, 385--390.

Digital Library

[59]

T. Rothvoss. 2011. Some 0/1 polytopes need exponential size extended formulations. arXiv:1105.0036.

[60]

T. Rothvoss. 2014. The matching polytope has exponential extension complexity. In Proceedings of STOC 2014. 263--272.

Digital Library

[61]

G. Schoenebeck, L. Trevisan, and M. Tulsiani. 2007. Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. In Proceedings of STOC 2007. 302--310.

Digital Library

[62]

A. Schrijver. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Springer-Verlag.

[63]

C. E. Shannon. 1949. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 25, 59--98.

[64]

H. D. Sherali and W. P. Adams. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Disc. Math. 3, 411--430.

Digital Library

[65]

M. Sipser. 1996. Introduction to the Theory of Computation. PWS, Boston, MA.

Digital Library

[66]

E. R. Swart. 1986; revision 1987. P = NP. Tech. rep., University of Guelph.

[67]

F. Vanderbeck and L. A. Wolsey. 2010. Reformulation and decomposition of integer programs. In 50 Years of Integer Programming 1958-2008, M. Jünger, Th, M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, Eds., Springer, 431--502.

[68]

R. de Wolf. 2002. Quantum communication and complexity. Theoret. Comput. Sci. 287, 337--353.

Digital Library

[69]

R. de Wolf. 2003. Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32, 681--699.

Digital Library

[70]

L. A. Wolsey. 2011. Using extended formulations in practice. Optima 85, 7--9.

[71]

M. Yannakakis. 1988. Expressing combinatorial optimization problems by linear programs (extended abstract). In Proceedings of STOC 1988. 223--228.

Digital Library

[72]

M. Yannakakis. 1991. Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci.43, 3, 441--466.

[73]

G. M. Ziegler. 1995. Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer-Verlag.

Cited By

Borgwardt SBrugger M(2024)Circuits in extended formulationsDiscrete Optimization10.1016/j.disopt.2024.10082552(100825)Online publication date: May-2024
https://doi.org/10.1016/j.disopt.2024.100825
Aprile MAverkov GDi Summa MHojny C(2024)The role of rationality in integer-programming relaxationsMathematical Programming: Series A and B10.1007/s10107-023-01994-w205:1-2(745-771)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10107-023-01994-w
Dong SRothvoss T(2024)The Extension Complexity of Polytopes with Bounded Integral Slack MatricesInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_9(113-123)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_9
Show More Cited By

Index Terms

Exponential Lower Bounds for Polytopes in Combinatorial Optimization
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Lower Bounds on the Size of Semidefinite Programming Relaxations
STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of ...
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we ...
On Interior-Point Warmstarts for Linear and Combinatorial Optimization

Despite the many advantages of interior-point algorithms over active-set methods for linear optimization, one of the remaining practical challenges is their current limitation to efficiently solve series of related problems by an effective warmstarting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 62, Issue 2

May 2015

304 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2772377

Editor:
Victor Vianu
University of California, San Diego

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 May 2015

Accepted: 01 January 2015

Revised: 01 November 2013

Received: 01 July 2012

Published in JACM Volume 62, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Interview
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

78
Total Citations
View Citations
1,001
Total Downloads

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

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Borgwardt SBrugger M(2024)Circuits in extended formulationsDiscrete Optimization10.1016/j.disopt.2024.10082552(100825)Online publication date: May-2024
https://doi.org/10.1016/j.disopt.2024.100825
Aprile MAverkov GDi Summa MHojny C(2024)The role of rationality in integer-programming relaxationsMathematical Programming: Series A and B10.1007/s10107-023-01994-w205:1-2(745-771)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10107-023-01994-w
Dong SRothvoss T(2024)The Extension Complexity of Polytopes with Bounded Integral Slack MatricesInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_9(113-123)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_9
Schade JSinha MWeltge S(2024)Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and KnapsackInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_28(379-392)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_28
Parekh O(2023)Synergies Between Operations Research and Quantum Information ScienceINFORMS Journal on Computing10.1287/ijoc.2023.126835:2(266-273)Online publication date: 9-Feb-2023
https://dl.acm.org/doi/10.1287/ijoc.2023.1268
Soh YVarvitsiotis A(2023)Multiplicative updates for symmetric-cone factorizationsMathematical Programming10.1007/s10107-023-02015-6207:1-2(427-456)Online publication date: 30-Sep-2023
https://doi.org/10.1007/s10107-023-02015-6
Schymura MSeidel IWeltge S(2023)Lifts for Voronoi Cells of LatticesDiscrete & Computational Geometry10.1007/s00454-023-00522-z70:3(845-865)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1007/s00454-023-00522-z
Steenkamp A(2023)Matrix Factorization Ranks Via Polynomial OptimizationPolynomial Optimization, Moments, and Applications10.1007/978-3-031-38659-6_5(153-180)Online publication date: 28-Dec-2023
https://doi.org/10.1007/978-3-031-38659-6_5
Brand CKoutecký MLassota A(2023)A Polyhedral Perspective on Tropical ConvolutionsCombinatorial Algorithms10.1007/978-3-031-34347-6_10(111-122)Online publication date: 3-Jun-2023
https://doi.org/10.1007/978-3-031-34347-6_10
Kim JTawarmalani MRichard J(2022)Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component AnalysisMathematics of Operations Research10.1287/moor.2021.121947:4(2547-2584)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/moor.2021.1219
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents