From weak to strong LP gaps for all CSPs
From MaRDI portal
Publication:5111141
DOI10.4230/LIPICS.CCC.2017.11zbMATH Open1440.68117arXiv1608.00497MaRDI QIDQ5111141FDOQ5111141
Authors: Mrinalkanti Ghosh, Madhur Tulsiani 
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/1608.00497
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
Convex programming (90C25) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)
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)
