From weak to strong linear programming gaps for all constraint satisfaction problems

DOI10.4086/TOC.2018.V014A010MaRDI QIDQ4568111zbMATH OpenOpenAlexFDO

Authors Mrinalkanti Ghosh, Madhur Tulsiani

Publication date 15 June 2018

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2018.v014a010

zbMATH Keywords

constraint satisfaction problemconvex programmingintegrality gaplinear programming hierarchy

Mathematics Subject Classification ID

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

Recommendations

• From weak to strong LP gaps for all CSPs
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• Approximating CSPs using LP relaxation
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Cites work

• A characterization of strong approximation resistance
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximating CSPs using LP relaxation
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• CSP gaps and reductions in the lasserre hierarchy
• Exponential lower bounds for polytopes in combinatorial optimization
• From weak to strong LP gaps for all CSPs
• Hardness of Graph Pricing Through Generalized Max-Dicut
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• Integrality gaps for Sherali-Adams relaxations
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Local global tradeoffs in metric embeddings
• Measured descent: A new embedding method for finite metrics
• Near-optimal algorithms for maximum constraint satisfaction problems
• On the efficient approximability of constraint satisfaction problems
• On the power of unique 2-prover 1-round games
• On the usefulness of predicates
• Proving integrality gaps without knowing the linear program
• SDP gaps from pairwise independence
• SDP Integrality Gaps with Local ell₁-Embeddability
• Sum of squares lower bounds for refuting any CSP
• The power of linear programming for general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy

Cited in

(10)

• Approximating CSPs using LP relaxation
• Optimal Sherali-Adams Gaps from Pairwise Independence
• 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
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• From weak to strong LP gaps for all CSPs
• Approximate graph colouring and the hollow shadow
• Approximate graph coloring and the crystal with a hollow shadow
• Semidefinite programming and linear equations vs. homomorphism problems
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems

This page was built for publication: From weak to strong linear programming gaps for all constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568111)