Exponential Lower Bounds for Polytopes in Combinatorial Optimization

DOI10.1145/2716307zbMath1333.90107arXiv1111.0837OpenAlexW1755753347MaRDI QIDQ2796404

Hans Raj Tiwary, Samuel Fiorini, Sebastian Pokutta, Serge Massar, Ronald de Wolf

Publication date: 24 March 2016

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingsemidefinite programmingcombinatorial optimizationcommunication complexityquantum communication complexity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Linear programming (90C05) Combinatorial optimization (90C27) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (62)

The rectangle covering number of random Boolean matrices ⋮ Sparktope: linear programs from algorithms ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Extension complexity of low-dimensional polytopes ⋮ Boolean quadric polytopes are faces of linear ordering polytopes ⋮ On the extension complexity of scheduling polytopes ⋮ The matching problem has no small symmetric SDP ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ Parameterized extension complexity of independent set and related problems ⋮ On the combinatorial lower bound for the extension complexity of the spanning tree polytope ⋮ Lifts for Voronoi cells of lattices ⋮ Around the log-rank conjecture ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ The parity Hamiltonian cycle problem ⋮ On Ranks of Regular Polygons ⋮ The role of rationality in integer-programming relaxations ⋮ Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes ⋮ 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 ⋮ Extension Complexity of Independent Set Polytopes ⋮ Unnamed Item ⋮ Parameterized low-rank binary matrix approximation ⋮ Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract) ⋮ Euclidean distance matrices and separations in communication complexity theory ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Extended formulations for order polytopes through network flows ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ Extension complexity and realization spaces of hypersimplices ⋮ Some upper and lower bounds on PSD-rank ⋮ Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Multipartite quantum correlation and communication complexities ⋮ Unnamed Item ⋮ Completely positive semidefinite rank ⋮ Unnamed Item ⋮ Extended formulations for vertex cover ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ Extension complexity of the correlation polytope ⋮ Balas formulation for the union of polytopes is optimal ⋮ Volume computation for sparse Boolean quadric relaxations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Pitch, extension complexity, and covering problems ⋮ On the linear extension complexity of stable set polytopes for perfect graphs ⋮ Polynomial size linear programs for problems in \textsc{P} ⋮ The Parity Hamiltonian Cycle Problem in Directed Graphs ⋮ A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extension complexity of formal languages ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Worst-case analysis of clique MIPs ⋮ 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 ⋮ On Polyhedral Approximations of the Positive Semidefinite Cone ⋮ New limits of treewidth-based tractability in optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Common information and unique disjointness
• Average case polyhedral complexity of the maximum stable set problem
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• On the extension complexity of combinatorial polytopes
• A new polynomial-time algorithm for linear programming
• Expressing combinatorial optimization problems by linear programs
• On the distributional complexity of disjointness
• Communication complexity and combinatorial lattice theory
• Combinatorial bounds on nonnegative rank and extended formulations
• The cut polytope and the Boolean quadric polytope
• Quantum communication and complexity.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Information-theoretic approximations of the nonnegative rank
• A short proof that the extension complexity of the correlation polytope grows exponentially
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A note on the extension complexity of the knapsack polytope
• On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Theta Bodies for Polynomial Ideals
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Lattice problems in NP ∩ coNP
• Reformulation and Decomposition of Integer Programs
• Symmetry Matters for the Sizes of Extended Formulations
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
• Optimal Sherali-Adams Gaps from Pairwise Independence
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Lectures on Polytopes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The Matching Polytope has Exponential Extension Complexity
• Nondeterministic Quantum Query and Communication Complexities
• Communication Complexity
• Lifts of Convex Sets and Cone Factorizations
• The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
• Integrality gaps for Sherali-Adams relaxations
• On the complexity of communication complexity
• Generalized probabilistic theories and conic extensions of polytopes
• Quantum Computer Science
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Lower Bounds for Local Search by Quantum Arguments
• An information complexity approach to extended formulations
• Extended formulations in combinatorial optimization
• Geometry of cuts and metrics
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

This page was built for publication: Exponential Lower Bounds for Polytopes in Combinatorial Optimization