Change search
ReferencesLink to record
Permanent link

Direct link
Is constraint satisfaction over two variables always easy?
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 25, no 2, 150-178 p.Article in journal (Refereed) Published
Abstract [en]

By the breakthrough work of Hastad [J ACM 48(4) (2001), 798-859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP-hard. This is the case for example for Max E3-Sat, Max E3-Lin, and Max E4-Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2-CSP); as a corollary of the celebrated Goemans-Williamson algorithm [J ACM 42(6) (1995), 1115-1145], we know that every Boolean 2-CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2-CSPs over larger, non-Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2-SAT to domains of size d, can be approximated to a factor better than (1 - 1/d(2)). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not-All-Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d greater than or equal to 3. In the Boolean case, Not-All-Equal Sat with three variables per constraint is equivalent to Max 2-SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2-SAT can be reduced to Not-All-Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2-CSPs called regular 2-CSPs can all be approximated beyond their random assignment threshold.

Place, publisher, year, edition, pages
2004. Vol. 25, no 2, 150-178 p.
National Category
Computer and Information Science Mathematics
URN: urn:nbn:se:kth:diva-40959DOI: 10.1002/rsa.20026ISI: 000223363800002ScopusID: 2-s2.0-11144262799OAI: diva2:443115
QC 20110923Available from: 2011-09-23 Created: 2011-09-23 Last updated: 2011-10-17Bibliographically 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
Random structures & algorithms (Print)
Computer and Information ScienceMathematics

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: 14 hits
ReferencesLink to record
Permanent link

Direct link