Exponential lower bounds for polytopes in combinatorial optimization
From MaRDI portal
Abstract: 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 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.
Recommendations
Cites work
- A counterexample to the Alon-Saks-Seymour conjecture and related problems
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A new polynomial-time algorithm for linear programming
- A note on the extension complexity of the knapsack polytope
- A short proof that the extension complexity of the correlation polytope grows exponentially
- An information complexity approach to extended formulations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Average case polyhedral complexity of the maximum stable set problem
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Common information and unique disjointness
- Communication Complexity
- Communication complexity and combinatorial lattice theory
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Expressing combinatorial optimization problems by linear programs
- Extended formulations in combinatorial optimization
- Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
- Generalized probabilistic theories and conic extensions of polytopes
- Geometry of cuts and metrics
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 1944141 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Information-theoretic approximations of the nonnegative rank
- Integrality gaps for Sherali-Adams relaxations
- Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
- Lattice problems in NP ∩ coNP
- Lectures on Polytopes
- Lifts of Convex Sets and Cone Factorizations
- Linear programming relaxations of \textsc{maxcut}
- Lower Bounds for Local Search by Quantum Arguments
- Lower bounds on the size of semidefinite programming relaxations
- Nondeterministic Quantum Query and Communication Complexities
- On the complexity of communication complexity
- On the distributional complexity of disjointness
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- On the Shannon capacity of a graph
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Quantum communication and complexity.
- Quantum Computer Science
- Rank bounds and integrality gaps for cutting planes procedures
- Reformulation and decomposition of integer programs
- Symmetry matters for the sizes of extended formulations
- The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
- The cut polytope and the Boolean quadric polytope
- Theta bodies for polynomial ideals
Cited in
(79)- Expressing combinatorial optimization problems by linear programs
- The matching problem has no small symmetric SDP
- The parity Hamiltonian cycle problem
- Euclidean distance matrices and separations in communication complexity theory
- Extended formulations for order polytopes through network flows
- Extension complexity and realization spaces of hypersimplices
- Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
- Completely positive semidefinite rank
- Extended formulations for vertex cover
- Lower bounds for maximal and convex layers problems
- Information-theoretic approximations of the nonnegative rank
- Multipartite quantum correlation and communication complexities
- Separation routine and extended formulations for the stable set problem in claw-free graphs
- Pitch, extension complexity, and covering problems
- Worst-case analysis of clique MIPs
- New limits of treewidth-based tractability in optimization
- Parameterized low-rank binary matrix approximation
- Strengthening convex relaxations of 0/1-sets using Boolean formulas
- Extension complexity of the correlation polytope
- Balas formulation for the union of polytopes is optimal
- Volume computation for sparse Boolean quadric relaxations
- On the linear extension complexity of stable set polytopes for perfect graphs
- Polynomial size linear programs for problems in \textsc{P}
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- The rectangle covering number of random Boolean matrices
- Boolean quadric polytopes are faces of linear ordering polytopes
- Parameterized extension complexity of independent set and related problems
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- On the extension complexity of scheduling polytopes
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Extended formulations for matroid polytopes through randomized protocols
- Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
- The parity Hamiltonian cycle problem in directed graphs
- A set covering approach for the double traveling salesman problem with multiple stacks
- Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
- Nondeterministic communication complexity of random Boolean functions (extended abstract)
- Extension complexity, MSO logic, and treewidth
- Average case polyhedral complexity of the maximum stable set problem
- From weak to strong linear programming gaps for all constraint satisfaction problems
- On ranks of regular polygons
- Extension complexity of independent set polytopes
- Small extended formulation for knapsack cover inequalities from monotone circuits
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- Parameterized low-rank binary matrix approximation
- On polyhedral approximations of the positive semidefinite cone
- Sparktope: linear programs from algorithms
- Lifting for simplicity: concise descriptions of convex sets
- Extension complexity of low-dimensional polytopes
- scientific article; zbMATH DE number 7559421 (Why is no real title available?)
- On the complexity of computing a random Boolean function over the reals
- Generalized probabilistic theories and conic extensions of polytopes
- Some upper and lower bounds on PSD-rank
- The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
- Forbidden vertices
- Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes
- Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis
- Lifts for Voronoi cells of lattices
- Around the log-rank conjecture
- Complex psd-minimal polytopes in dimensions two and three
- The role of rationality in integer-programming relaxations
- On the extension complexity of polytopes separating subsets of the Boolean cube
- On permuting some coordinates of polytopes
- A polyhedral perspective on tropical convolutions
- Tensor decompositions on simplicial complexes with invariance
- Circuits in extended formulations
- Multiplicative updates for symmetric-cone factorizations
- Piecewise polyhedral relaxations of multilinear optimization
- Binary cyclic transversal polytopes
- Matrix factorization ranks via polynomial optimization
- Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
- The extension complexity of polytopes with bounded integral slack matrices
- Sublinear extensions of polygons
- Communication memento: memoryless communication complexity
- Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
- Extension complexity of formal languages
This page was built for publication: Exponential lower bounds for polytopes in combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796404)
