Samuel Fiorini
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
html
auxiliary.html (748 B)
Note about the resolution of an open question in Section 5 (unrefereed material)
- S. Aaronson. 2006. Lower bounds for local search by quantum arguments. SIAM J. Comput. 35, 4, 804--824. (Earlier version in STOC'04). Google Scholar
Digital Library
- D. Aharonov and O. Regev. 2004. Lattice problems in NP ∩ coNP. In Proceedings of FOCS 2004. 362--371. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- D. Avis and H. R. Tiwary. 2013. On the Extension Complexity of Combinatorial Polytopes. In Proceedings of ICALP(1) 2013. 57--68. Google ScholarDigital Library
- E. Balas. 1985. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algeb. Disc. Meth. 6, 466--486.Google ScholarDigital Library
- E. Balas, S. Ceria, and G. Cornuéjols. 1993. A lift-and-project algorithm for mixed 0-1 programs. Math. Prog. 58, 295--324. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. Braun, S. Fiorini, S. Pokutta, and D. Steurer. 2012. Approximation limits of linear programs (beyond hierarchies). In Proceedings of FOCS 2012. 480--489. Google ScholarDigital Library
- G. Braun, S. Fiorini, and S. Pokutta. 2013a. Average case polyhedral complexity of the maximum stable set problem. arXiv:1311.4001.Google Scholar
- G. Braun, R. Jain, T. Lee, and S. Pokutta. 2013b. Information-theoretic approximations of the nonnegative rank. ECCC Report no. 158 (2013).Google Scholar
- G. Braun and S. Pokutta. 2013. Common information and unique disjointness. In Proceedings of FOCS 2013. 688--697. Google ScholarDigital Library
- M. Braverman and A. Moitra. 2013. An information complexity approach to extended formulations. In Proceedings of STOC 2013. 161--170. Google ScholarDigital Library
- 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.Google Scholar
- H. Buhrman, R. Cleve, S. Massar, and R. de Wolf. 2010. Nonlocality and communication complexity. Rev. Modern Phys. 82, 665.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- M. Charikar, K. Makarychev, and Y. Makarychev. 2009. Integrality gaps for Sherali-Adams relaxations. In Proceedings of STOC 2009. 283--292. Google ScholarDigital Library
- M. Conforti, G. Cornuéjols, and G. Zambelli. 2010. Extended formulations in combinatorial optimization. 4OR 8, 1--48.Google Scholar
- 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.Google Scholar
- C. De Simone. 1990. The cut polytope and the Boolean quadric polytope. Disc. Math. 79, 71--75. Google ScholarDigital Library
- M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Algorithms and Combinatorics Series, vol. 15, Springer-Verlag. Google ScholarDigital Library
- A. Drucker and R. de Wolf. 2011. Quantum proofs for classical theorems. Theory Comput. Graduate Surveys 2.Google Scholar
- Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary. 2011. Extended formulations, non-negative factorizations and randomized communication protocols. arXiv:1105.4127.Google Scholar
- H. Fawzi and P. A. Parrilo. 2013. Exponential lower bounds on fixed-size PSD rank and semidefinite extension complexity. arXiv:1311.2571.Google Scholar
- W. Fernandez de la Vega and C. Mathieu. 2007. Linear programming relaxation of Maxcut. In Proceedings of SODA 2007. 53--61. Google ScholarDigital Library
- S. Fiorini, V. Kaibel, K. Pashkovich, and D. O. Theis. 2011. Combinatorial bounds on nonnegative rank and extended formulations. arXiv:1111.0444.Google Scholar
- S. Fiorini, S. Massar, M. K. Patra, and H. R. Tiwary. 2013. Generalised probabilistic theories and conic extensions of polytopes. CoRR abs/1310.4125.Google Scholar
- 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. Google ScholarDigital Library
- K. Georgiou, A. Magen, and M. Tulsiani. 2009. Optimal Sherali-Adams gaps from pairwise independence. In Proceedings of APPROX-RANDOM 2009. 125--139. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Gouveia, P. A. Parrilo, and R. R. Thomas. 2010. Theta bodies for polynomial ideals. SIAM J. Optim. 20, 2097--2118. Google ScholarDigital Library
- J. Gouveia, P. A. Parrilo, and R. R. Thomas. 2013. Lifts of convex sets and cone factorizations. Math. Oper. Res.38, 2, 248--264. Google ScholarDigital Library
- J. Håstad. 1999. Clique is Hard to Approximate within n1&mins;ε. Acta Math. 182, 105--142. (Earlier version in Proceedings of FOCS 1996.)Google ScholarCross Ref
- H. Huang and B. Sudakov. 2012. A counterexample to the Alon-Saks-Seymour conjecture and related problems. Combinatorica32, 2, 205--219. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- V. Kaibel. 2011. Extended formulations in combinatorial optimization. Optima 85, 2--7.Google Scholar
- V. Kaibel, K. Pashkovich, and D. O. Theis. 2010. Symmetry matters for the sizes of extended formulations. In Proceedings of IPCO 2010. 135--148. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- N. Karmarkar. 1984. A new polynomial time algorithm for linear programming. Combinatorica 4, 373--395. Google ScholarDigital Library
- 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). Google ScholarDigital Library
- L. G. Khachiyan. 1979. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR244, 5, 1093--1096.Google Scholar
- S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. 2007. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput.37, 1, 319--357. Google ScholarDigital Library
- 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.Google Scholar
- E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- E. Kushilevitz and E. Weinreb. 2009b. On the complexity of communication complexity. In Proceedings of STOC 2009. 465--474. Google ScholarDigital Library
- J. R. Lee, P. Raghavendra, and D. Steurer. 2015. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of STOC 2015.Google Scholar
- T. Lee and D. O. Theis. 2012. Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix. arXiv:1203.3961.Google Scholar
- L. Lovász. 1979. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1--7. Google ScholarDigital Library
- 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.Google Scholar
- L. Lovász and M. Saks. 1993. Communication complexity and combinatorial lattice theory. J. Comput. Syst. Sci. 47, 322--349. Google ScholarDigital Library
- L. Lovász and A. Schrijver. 1991. Cones of matrices and set-functions and 0&mins;1 optimization. SIAM J. Optim. 1, 166--190.Google ScholarDigital Library
- N. D. Mermin. 2007. Quantum Computer Science: An Introduction. Cambridge University Press. Google ScholarDigital Library
- M. A. Nielsen and I. L. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press. Google ScholarDigital Library
- K. Pashkovich. 2009. Symmetry in extended formulations of the permutahedron. arXiv:0912.3446.Google Scholar
- S. Pokutta and M. Van Vyve. 2013. A note on the extension complexity of the knapsack polytope. Oper. Res. Lett.41, 4, 347--350.Google ScholarCross Ref
- A. A. Razborov. 1992. On the distributional complexity of disjointness. Theoret. Comput. Sci.106, 2, 385--390. Google ScholarDigital Library
- T. Rothvoss. 2011. Some 0/1 polytopes need exponential size extended formulations. arXiv:1105.0036.Google Scholar
- T. Rothvoss. 2014. The matching polytope has exponential extension complexity. In Proceedings of STOC 2014. 263--272. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. Schrijver. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Springer-Verlag.Google Scholar
- C. E. Shannon. 1949. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 25, 59--98.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- M. Sipser. 1996. Introduction to the Theory of Computation. PWS, Boston, MA. Google ScholarDigital Library
- E. R. Swart. 1986; revision 1987. P = NP. Tech. rep., University of Guelph.Google Scholar
- 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.Google Scholar
- R. de Wolf. 2002. Quantum communication and complexity. Theoret. Comput. Sci. 287, 337--353. Google ScholarDigital Library
- R. de Wolf. 2003. Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32, 681--699. Google ScholarDigital Library
- L. A. Wolsey. 2011. Using extended formulations in practice. Optima 85, 7--9.Google Scholar
- M. Yannakakis. 1988. Expressing combinatorial optimization problems by linear programs (extended abstract). In Proceedings of STOC 1988. 223--228. Google ScholarDigital Library
- M. Yannakakis. 1991. Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci.43, 3, 441--466.Google ScholarCross Ref
- G. M. Ziegler. 1995. Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer-Verlag.Google Scholar
Index Terms
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
Recommendations
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingWe 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 ...
A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem
AbstractWe investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point ...
Comments