2026-07-26T21:06:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6638 2024-03-06T10:38:34Z ddc:004 open_access

Near-Optimal UGC-hardness of Approximating Max k-CSP_R Manurangsi, Pasin Nakkiran, Preetum Trevisan, Luca inapproximability unique games conjecture constraint satisfaction problem invariance principle In this paper, we prove an almost-optimal hardness for Max k-CSP_R based on Khot's Unique Games Conjecture (UGC). In Max k-CSP_R, we are given a set of predicates each of which depends on exactly k variables. Each variable can take any value from 1, 2, ..., R. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max k-CSP_R to within factor 2^{O(k log k)}(log R)^{k/2}/R^{k - 1} for any k, R. To the best of our knowledge, this result improves on all the known hardness of approximation results when 3 <= k = o(log R/log log R). In this case, the previous best hardness result was NP-hardness of approximating within a factor O(k/R^{k-2}) by Chan. When k = 2, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell. In addition, by extending an algorithm for Max 2-CSP_R by Kindler, Kolla and Trevisan, we provide an Omega(log R/R^{k - 1})-approximation algorithm for Max k-CSP_R. This algorithm implies that our inapproximability result is tight up to a factor of 2^{O(k \log k)}(\log R)^{k/2 - 1}. In comparison, when 3 <= k is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of O(polylog R). Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's d-to-1 Conjecture and still get asymptotically the same hardness of approximation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pasin Manurangsi and Preetum Nakkiran and Luca Trevisan 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.15 urn:nbn:de:0030-drops-66388 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.15 eng https://creativecommons.org/licenses/by/3.0/legalcode