The matching problem has no small symmetric SDP

DOI10.1007/S10107-016-1098-ZzbMATH Open1373.90094arXiv1504.00703OpenAlexW3137878162MaRDI QIDQ1675264FDOQ1675264

Authors: Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink 

Publication date: 27 October 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo{ss} recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size $n^k$. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.

Full work available at URL: https://arxiv.org/abs/1504.00703

Recommendations

• The matching problem has no small symmetric SDP
• On the Power of Symmetric Linear Programs
• Lower bounds on the size of semidefinite programming relaxations
• Expressing combinatorial optimization problems by linear programs
• Symmetry matters for the sizes of extended formulations

zbMATH Keywords

semidefinite programmingextended formulationsmatching problemTSP problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Semidefinite Programming
• Title not available (Why is that?)
• Expressing combinatorial optimization problems by linear programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Linear vs. semidefinite extended formulations
• Maximum matching and a polyhedron with 0,1-vertices
• Lifts of Convex Sets and Cone Factorizations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Smallest compact formulation for the permutahedron
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• An information complexity approach to extended formulations
• Exponential lower bounds for polytopes in combinatorial optimization
• Inapproximability of combinatorial problems via small LPs and SDPs
• Lower bounds on the size of semidefinite programming relaxations
• The matching polytope does not admit fully-polynomial size relaxation schemes
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• An algebraic approach to symmetric extended formulations
• Symmetry matters for the sizes of extended formulations
• Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• The Matching Problem Has No Fully Polynomial Size Linear Programming Relaxation Schemes
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)

Cited In (6)

• Perfect matching in random graphs is as hard as Tseitin
• Sum-of-squares rank upper bounds for matching problems
• The matching problem has no small symmetric SDP
• Sum-of-squares rank upper bounds for matching problems
• On the power of symmetric linear programs
• On the Power of Symmetric Linear Programs

This page was built for publication: The matching problem has no small symmetric SDP

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