Approximate Constraint Satisfaction Requires Large LP Relaxations
From MaRDI portal
Abstract: We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.
Recommendations
- On approximate constraint satisfaction
- The approximability of constraint satisfaction problems
- Approximating CSPs using LP relaxation
- On the efficient approximability of constraint satisfaction problems
- Simultaneous approximation of constraint satisfaction problems
- Randomized approximation of the constraint satisfaction problem
- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
- scientific article; zbMATH DE number 1002207
- An LP-Designed Algorithm for Constraint Satisfaction
- Approximability of constrained LCS
Cited in
(68)- Sum-of-squares rank upper bounds for matching problems
- The matching problem has no small symmetric SDP
- Affine reductions for LPs and SDPs
- Simple approximation algorithms for balanced MAX~2SAT
- Approximating graph-constrained max-cut
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Information-theoretic approximations of the nonnegative rank
- Balas formulation for the union of polytopes is optimal
- Parameterized extension complexity of independent set and related problems
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- A comprehensive analysis of polyhedral lift-and-project methods
- Exponential lower bounds for polytopes in combinatorial optimization
- Sum-of-squares rank upper bounds for matching problems
- Linear programming relaxations of \textsc{maxcut}
- Inapproximability of combinatorial problems via small LPs and SDPs
- Lower bounds on the size of semidefinite programming relaxations
- Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
- Separation between estimation and approximation
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Common information and unique disjointness
- Query complexity in expectation
- Approximating CSPs using LP relaxation
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Average case polyhedral complexity of the maximum stable set problem
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Communication lower bounds via critical block sensitivity
- Deterministic communication vs. partition number
- From weak to strong linear programming gaps for all constraint satisfaction problems
- LP relaxations of some NP-hard problems are as hard as any LP
- 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
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- Superlinear Integrality Gaps for the Minimum Majority Problem
- Reflections on Proof Complexity and Counting Principles
- Lifting for simplicity: concise descriptions of convex sets
- Extension complexity of low-dimensional polytopes
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- Sherali-adams strikes back
- From weak to strong LP gaps for all CSPs
- Query-to-communication lifting for BPP
- scientific article; zbMATH DE number 7250155 (Why is no real title available?)
- Sherali-Adams strikes back
- Integrality gaps for Sherali-Adams relaxations
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- Constant-query testability of assignments to constraint satisfaction problems
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- The complexity of general-valued CSPs
- The power of Sherali-Adams relaxations for general-valued CSPs
- An almost optimal algorithm for computing nonnegative rank
- Rectangles are nonnegative juntas
- Principles and Practice of Constraint Programming – CP 2004
- A tight approximation algorithm for the cluster vertex deletion problem
- Lifts for Voronoi cells of lattices
- Sum-of-squares lower bounds for densest k-subgraph
- Approximate graph colouring and the hollow shadow
- Perfect matching in random graphs is as hard as Tseitin
- Approximate graph coloring and the crystal with a hollow shadow
- Instance-specific linear relaxations of semidefinite optimization problems
- Semidefinite programming and linear equations vs. homomorphism problems
- Sublinear extensions of polygons
- On Fourier analysis of sparse Boolean functions over certain abelian groups
- Towards PNP from extended Frege lower bounds
- Extension complexity of formal languages
- Extended formulation for CSP that is compact for instances of bounded treewidth
This page was built for publication: Approximate Constraint Satisfaction Requires Large LP Relaxations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177811)
