Approximating CSPs Using LP Relaxation

DOI10.1007/978-3-662-47672-7_67zbMath1440.68103OpenAlexW2405977959MaRDI QIDQ3448840

Subhash A. 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)

Related Items (4)

Approximating CSPs Using LP Relaxation ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Noise stability of functions with low influences: invariance and optimality
• Parallel approximation algorithms by positive linear programming
• Gaussian bounds for noise correlation of functions
• Linear programming, width-1 CSPs, and robust satisfaction
• Near-optimal algorithms for unique games
• Approximating CSPs Using LP Relaxation
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Approximation of non-boolean 2CSP
• Towards a Characterization of Constant-Factor Approximable Min CSPs
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Approximation resistance from pairwise independent subgroups

This page was built for publication: Approximating CSPs Using LP Relaxation