Approximating CSPs using LP relaxation

DOI10.1007/978-3-662-47672-7_67MaRDI QIDQ3448840zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Rishi Saket

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47672-7_67

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• From weak to strong LP gaps for all CSPs
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• From weak to strong linear programming gaps for all constraint satisfaction problems
• On LP-based approximability for strict CSPs
• Towards a characterization of constant-factor approximable min CSPs

Cites work

• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• Approximating CSPs using LP relaxation
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Approximation of non-Boolean 2CSP
• Approximation resistance from pairwise independent subgroups
• Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four
• Gaussian bounds for noise correlation of functions
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Linear programming, width-1 CSPs, and robust satisfaction
• Near-optimal algorithms for unique games
• Noise stability of functions with low influences: invariance and optimality
• On LP-based approximability for strict CSPs
• On the optimality of the random hyperplane rounding technique for MAX CUT
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Parallel approximation algorithms by positive linear programming
• Towards a characterization of constant-factor approximable min CSPs

Cited in

(16)

• Approximate Constraint Satisfaction Requires Large LP Relaxations
• On LP-based approximability for strict CSPs
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• CSP gaps and reductions in the lasserre hierarchy
• Complexity and approximability of parameterized MAX-CSPs
• From weak to strong linear programming gaps for all constraint satisfaction problems
• From weak to strong LP gaps for all CSPs
• Approximate Lasserre integrality gap for unique games
• LP relaxations of some NP-hard problems are as hard as any LP
• Approximation Algorithms for CSPs
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Approximating CSPs using LP relaxation
• Solving RCPSP/max by lazy clause generation
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• Towards a characterization of constant-factor approximable min CSPs
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

This page was built for publication: Approximating CSPs using LP relaxation

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