Approximating CSPs Using LP Relaxation
From MaRDI portal
Publication:3448840
DOI10.1007/978-3-662-47672-7_67zbMath1440.68103MaRDI QIDQ3448840
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Unnamed Item, Complexity and approximability of parameterized MAX-CSPs, Approximating CSPs Using LP Relaxation
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