Approximate Constraint Satisfaction Requires Large LP Relaxations
From MaRDI portal
(Redirected from Publication:3177811)
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
(67)- Principles and Practice of Constraint Programming – CP 2004
- Information-theoretic approximations of the nonnegative rank
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
- Reflections on Proof Complexity and Counting Principles
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Sherali-adams strikes back
- Lifting for simplicity: concise descriptions of convex sets
- Perfect matching in random graphs is as hard as Tseitin
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Sublinear extensions of polygons
- A tight approximation algorithm for the cluster vertex deletion problem
- Exponential lower bounds for polytopes in combinatorial optimization
- Simple approximation algorithms for balanced MAX~2SAT
- Sum-of-squares rank upper bounds for matching problems
- Rectangles are nonnegative juntas
- From weak to strong linear programming gaps for all constraint satisfaction problems
- scientific article; zbMATH DE number 7250155 (Why is no real title available?)
- Constant-query testability of assignments to constraint satisfaction problems
- From weak to strong LP gaps for all CSPs
- Lifts for Voronoi cells of lattices
- The power of Sherali-Adams relaxations for general-valued CSPs
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Common information and unique disjointness
- Extension complexity of low-dimensional polytopes
- Integrality gaps for Sherali-Adams relaxations
- Approximating graph-constrained max-cut
- Sum-of-squares rank upper bounds for matching problems
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- LP relaxations of some NP-hard problems are as hard as any LP
- Deterministic communication vs. partition number
- The complexity of general-valued CSPs
- Query-to-communication lifting for BPP
- On Fourier analysis of sparse Boolean functions over certain abelian groups
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Small extended formulation for knapsack cover inequalities from monotone circuits
- Query complexity in expectation
- The matching problem has no small symmetric SDP
- Parameterized extension complexity of independent set and related problems
- Average case polyhedral complexity of the maximum stable set problem
- Approximating CSPs using LP relaxation
- Extension complexity of formal languages
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Linear programming relaxations of \textsc{maxcut}
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- A comprehensive analysis of polyhedral lift-and-project methods
- An almost optimal algorithm for computing nonnegative rank
- Towards PNP from extended Frege lower bounds
- Extension complexity of independent set polytopes
- Approximate graph colouring and the hollow shadow
- Sum-of-squares lower bounds for densest k-subgraph
- Separation between estimation and approximation
- Instance-specific linear relaxations of semidefinite optimization problems
- Approximate graph coloring and the crystal with a hollow shadow
- Semidefinite programming and linear equations vs. homomorphism problems
- Sherali-Adams strikes back
- Balas formulation for the union of polytopes is optimal
- Inapproximability of combinatorial problems via small LPs and SDPs
- Lower bounds on the size of semidefinite programming relaxations
- Communication lower bounds via critical block sensitivity
- Affine reductions for LPs and SDPs
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)
