Approximation of non-Boolean 2CSP

DOI10.1137/1.9781611974331.CH117zbMATH Open1410.68171arXiv1504.00681OpenAlexW2953269844MaRDI QIDQ4575701FDOQ4575701

Authors: Guy Kindler, Alexandra Kolla, Luca Trevisan 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We develop a polynomial time $Omegaleft(frac1RlogRight)$ approximate algorithm for Max 2CSP-$R$, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size $R$, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a $1/R$-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming (SDP) and on a novel rounding technique. The SDP that we use has an almost-matching integrality gap.

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

Recommendations

• Every 2-CSP allows nontrivial approximation
• Every 2-CSP allows nontrivial approximation
• Approximation algorithm for non-Boolean MAX \(k\)-CSP
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• scientific article

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Approximation algorithms (68W25)

Cited In (12)

• Approximating dense MAX 2-CSPs
• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Every 2-CSP allows nontrivial approximation
• Approximation algorithm for non-Boolean MAX \(k\)-CSP
• Fast SDP algorithms for constraint satisfaction problems
• Towards sharp inapproximability for any 2-CSP
• Approximation Algorithms for CSPs
• Approximating CSPs using LP relaxation
• Every 2-CSP allows nontrivial approximation
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

This page was built for publication: Approximation of non-Boolean 2CSP

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