From weak to strong LP gaps for all CSPs

DOI10.4230/LIPICS.CCC.2017.11MaRDI QIDQ5111141zbMATH OpenFDO

Authors Mrinalkanti Ghosh, Madhur Tulsiani

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1608.00497

zbMATH Keywords

convex programmingintegrality gapconstraint satisfaction problemlinear programming hierarchy

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Recommendations

• From weak to strong linear programming gaps for all constraint satisfaction problems
• 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

Cited in

(9)

• Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
• On LP-based approximability for strict CSPs
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Optimal Sherali-Adams Gaps from Pairwise Independence
• CSP gaps and reductions in the lasserre hierarchy
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Approximating CSPs using LP relaxation
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• Towards a characterization of constant-factor approximable min CSPs

This page was built for publication: From weak to strong LP gaps for all CSPs

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