Change search
ReferencesLink to record
Permanent link

Direct link
The nonapproximability of non-Boolean predicates
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
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
Abstract [en]

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.
Keyword [en]
combinatorial optimization, approximation, approximation hardness, maximum CSP
National Category
URN: urn:nbn:se:kth:diva-45890DOI: 10.1137/S0895480100380458ISI: 000224348700009ScopusID: 2-s2.0-14644432405OAI: diva2:453177
QC 20111101Available from: 2011-11-01 Created: 2011-11-01 Last updated: 2011-11-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engebretsen, Lars
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
SIAM Journal on Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link