Approximate Constraint Satisfaction Requires Large LP Relaxations
From MaRDI portal
Publication:3177811
DOI10.1145/2811255zbMath1394.68170arXiv1309.0563OpenAlexW2963010019MaRDI QIDQ3177811
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)
Full work available at URL: https://arxiv.org/abs/1309.0563
lower boundsconstraint satisfaction problemsapproximation complexityLP hierarchieslinear programming, extended formulations
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The Complexity of General-Valued CSPs, Lifting for Simplicity: Concise Descriptions of Convex Sets, Query Complexity in Expectation, Sum-of-squares rank upper bounds for matching problems, Approximation Limits of Linear Programs (Beyond Hierarchies), Integrality gaps for strengthened linear relaxations of capacitated facility location, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Communication Lower Bounds via Critical Block Sensitivity, Common information and unique disjointness, Average case polyhedral complexity of the maximum stable set problem, Deterministic Communication vs. Partition Number, Extension complexity of low-dimensional polytopes, The matching problem has no small symmetric SDP, Parameterized extension complexity of independent set and related problems, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Lifts for Voronoi cells of lattices, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), Extended formulation for CSP that is compact for instances of bounded treewidth, Query-to-Communication Lifting for BPP, Extension Complexity of Independent Set Polytopes, Affine reductions for LPs and SDPs, Simple approximation algorithms for balanced MAX~2SAT, An Almost Optimal Algorithm for Computing Nonnegative Rank, Information-theoretic approximations of the nonnegative rank, Unnamed Item, Unnamed Item, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Unnamed Item, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Rectangles Are Nonnegative Juntas, Approximating graph-constrained max-cut, Semidefinite and linear programming integrality gaps for scheduling identical machines, Strong reductions for extended formulations, Extended formulations from communication protocols in output-efficient time, Balas formulation for the union of polytopes is optimal, A tight approximation algorithm for the cluster vertex deletion problem, Unnamed Item, Sherali-adams strikes back, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, Sum-of-Squares Rank Upper Bounds for Matching Problems, Unnamed Item, Extension complexity of formal languages, Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs, Unnamed Item, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, Reflections on Proof Complexity and Counting Principles
