The nonapproximability of non-Boolean predicates
2004 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 18, no 1, 114-129 p.Article in journal (Refereed) Published
Constraint satisfaction programs where each constraint depends on a constant number of variables have the following property: The randomized algorithm that guesses an assignment uniformly at random satisfies an expected constant fraction of the constraints. Combining constructions from interactive proof systems with harmonic analysis over finite Abelian groups, Hastad [J. ACM, 48 ( 2001), pp. 798 - 859] showed that for several constraint satisfaction programs this naive algorithm is essentially the best possible unless P = NP. While most of the predicates analyzed by Hastad depend on a small number of variables, Samorodnitsky and Trevisan [ Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 191 - 199] recently extended Hastad's result to predicates depending on an arbitrarily large, but still constant, number of Boolean variables. We combine ideas from these two constructions and prove that there exists a large class of predicates on finite non-Boolean domains such that for predicates in the class, the naive randomized algorithm that guesses a solution uniformly is essentially the best possible unless P = NP. As a corollary, we show that it is NP-hard to approximate the Maximum k-CSP problem over domains with size d within d(k-2k1/2) - epsilon, for every constant epsilon > 0, unless P = NP. This lower bound extends the previously known bound for the case d = 2 and matches well with the best known upper bound, d(k-1), of Serna, Trevisan, and Xhafa [ Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 1373, M. Morvan, C. Meinel, and D. Krob, eds., Springer-Verlag, Berlin, 1998, pp. 488 - 498].
Place, publisher, year, edition, pages
2004. Vol. 18, no 1, 114-129 p.
combinatorial optimization, approximation, approximation hardness, maximum CSP
IdentifiersURN: urn:nbn:se:kth:diva-45890DOI: 10.1137/S0895480100380458ISI: 000224348700009ScopusID: 2-s2.0-14644432405OAI: oai:DiVA.org:kth-45890DiVA: diva2:453177
QC 201111012011-11-012011-11-012011-11-01Bibliographically approved