Approximate Constraint Satisfaction Requires Large LP Relaxations
From MaRDI portal
Publication:3177811
DOI10.1145/2811255zbMATH Open1394.68170arXiv1309.0563OpenAlexW2963010019MaRDI QIDQ3177811FDOQ3177811
Authors: Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer 
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1309.0563
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
lower boundsconstraint satisfaction problemsapproximation complexityLP hierarchieslinear programming, extended formulations
Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (63)
- Perfect matching in random graphs is as hard as Tseitin
- Lifts for Voronoi cells of lattices
- Approximate graph colouring and the hollow shadow
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Strong reductions for extended formulations
- Information-theoretic approximations of the nonnegative rank
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
- Reflections on Proof Complexity and Counting Principles
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- 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
- 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
- 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
- Rectangles are nonnegative juntas
- Sum-of-squares rank upper bounds for matching problems
- From weak to strong linear programming gaps for all constraint satisfaction problems
- Title not available (Why is that?)
- Constant-query testability of assignments to constraint satisfaction problems
- From weak to strong LP gaps for all CSPs
- The power of Sherali-Adams relaxations for general-valued CSPs
- Extension complexity of low-dimensional polytopes
- Integrality gaps for Sherali-Adams relaxations
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Sum-of-squares rank upper bounds for matching problems
- Common information and unique disjointness
- Approximating graph-constrained max-cut
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- The complexity of general-valued CSPs
- LP relaxations of some NP-hard problems are as hard as any LP
- Deterministic communication vs. partition number
- Query-to-communication lifting for BPP
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Small extended formulation for knapsack cover inequalities from monotone circuits
- Title not available (Why is that?)
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Query complexity in expectation
- Extended formulations from communication protocols in output-efficient time
- Parameterized extension complexity of independent set and related problems
- The matching problem has no small symmetric SDP
- Average case polyhedral complexity of the maximum stable set problem
- Approximating CSPs using LP relaxation
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Extension complexity of formal languages
- Linear programming relaxations of \textsc{maxcut}
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- An almost optimal algorithm for computing nonnegative rank
- Extension complexity of independent set polytopes
- A comprehensive analysis of polyhedral lift-and-project methods
- Separation between estimation and approximation
- Communication lower bounds via critical block sensitivity
- Inapproximability of combinatorial problems via small LPs and SDPs
- Lower bounds on the size of semidefinite programming relaxations
- Balas formulation for the union of polytopes is optimal
- Principles and Practice of Constraint Programming – CP 2004
- 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)
