Manurangsi, Pasin ;
Nakkiran, Preetum ;
Trevisan, Luca
NearOptimal UGChardness of Approximating Max kCSP_R
Abstract
In this paper, we prove an almostoptimal hardness for Max kCSP_R based on Khot's Unique Games Conjecture (UGC). In Max kCSP_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 NPhard to approximate Max kCSP_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 NPhardness of approximating within a factor O(k/R^{k2}) by Chan. When k = 2, our result matches the best known UGChardness result of Khot, Kindler, Mossel and O'Donnell.
In addition, by extending an algorithm for Max 2CSP_R by Kindler, Kolla and Trevisan, we provide an Omega(log R/R^{k  1})approximation algorithm for Max kCSP_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 dto1 Conjecture and still get asymptotically the same hardness of approximation.
BibTeX  Entry
@InProceedings{manurangsi_et_al:LIPIcs:2016:6638,
author = {Pasin Manurangsi and Preetum Nakkiran and Luca Trevisan},
title = {{NearOptimal UGChardness of Approximating Max kCSP_R}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {15:115:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6638},
URN = {urn:nbn:de:0030drops66388},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.15},
annote = {Keywords: inapproximability, unique games conjecture, constraint satisfaction problem, invariance principle}
}
06.09.2016
Keywords: 

inapproximability, unique games conjecture, constraint satisfaction problem, invariance principle 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

06.09.2016 