Approximate Constraint Satisfaction Requires Large LP Relaxations

DOI10.1145/2811255zbMATH Open1394.68170arXiv1309.0563OpenAlexW2963010019MaRDI QIDQ3177811FDOQ3177811

Prasad Raghavendra, James R. Lee, David Steurer, Siu On Chan

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

zbMATH Keywords

lower boundsconstraint satisfaction problemsapproximation complexityLP hierarchieslinear programming, extended formulations

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (50)

• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Strong reductions for extended formulations
• Information-theoretic approximations of the nonnegative rank
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reflections on Proof Complexity and Counting Principles
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Perfect matching in random graphs is as hard as Tseitin
• Sherali-adams strikes back
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Query-to-Communication Lifting for BPP
• The Complexity of General-Valued CSPs
• Title not available (Why is that?)
• 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
• Extension Complexity of Independent Set Polytopes
• Sum-of-squares rank upper bounds for matching problems
• Title not available (Why is that?)
• Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs
• Lifts for Voronoi cells of lattices
• Sum-of-Squares Rank Upper Bounds for Matching Problems
• Extension complexity of low-dimensional polytopes
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• Common information and unique disjointness
• Approximating graph-constrained max-cut
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• Title not available (Why is that?)
• Extended formulation for CSP that is compact for instances of bounded treewidth
• 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
• Lifting for Simplicity: Concise Descriptions of Convex Sets
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Extension complexity of formal languages
• A comprehensive analysis of polyhedral lift-and-project methods
• Approximate graph colouring and the hollow shadow
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Communication Lower Bounds via Critical Block Sensitivity
• Title not available (Why is that?)
• Query Complexity in Expectation
• Constant-Query Testability of Assignments to Constraint Satisfaction Problems
• Balas formulation for the union of polytopes is optimal
• Principles and Practice of Constraint Programming – CP 2004
• Affine reductions for LPs and SDPs
• Deterministic Communication vs. Partition Number

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)