\input zb-basic
\input zb-ioport
\iteman{io-port 05837595}
\itemau{Austrin, Per}
\itemti{Towards sharp inapproximability for any 2-CSP.}
\itemso{SIAM J. Comput. 39, No. 6, 2430-2463 (2010).}
\itemab
Summary: We continue the recent line of work on the connection between semidefinite programming (SDP)-based approximation algorithms and the unique games conjecture. Given any Boolean 2-CSP (or, more generally, any Boolean 2-CSP with real-valued``predicates"), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. Furthermore, we give an SDP-based approximation algorithm and show that the approximation ratio of this algorithm on a certain restricted type of instances is exactly the inapproximability ratio yielded by our hardness result. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-And is unique games-hard to approximate within 0.87435. This improves upon the best previous hardness of $\alpha_{GW}+\epsilon\approx 0.87856$ and comes very close to matching the approximation ratio of 0.87401 of the best algorithm known. It also establishes that balanced instances of Max 2-And, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor $\alpha_{GW}$, and that Max Cut is not the hardest 2-CSP.
\itemrv{~}
\itemcc{}
\itemut{constraint satisfaction problems; approximation algorithms; unique games conjecture; semidefinite programming; CSP}
\itemli{doi:10.1137/070711670}
\end