Approximation of non-Boolean 2CSP

DOI10.1137/1.9781611974331.CH117MaRDI QIDQ4575701zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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; zbMATH DE number 6381632

Cited in

(13)

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

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)