EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION
2008 (English)In: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 17, no 4, 549-566 p.Article in journal (Refereed) Published
We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does better than picking a random assignment. Specifically we consider the case when each variable can take values in [d] and that each constraint rejects t out of the d(2) possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, in expectation, within a factor 1 - t/d(2) + ct/d(4) log d of optimal, improving on the trivial bound of 1 - t/d(2).
Place, publisher, year, edition, pages
2008. Vol. 17, no 4, 549-566 p.
Semi-definite programming, constraint satisfaction, approximation, algorithms, combinatorial optimization, constraint satisfaction, satisfiability, problems, linear-equations, 2 variables, semidefinite, algorithms, cut
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-18021DOI: 10.1007/s00037-008-0256-yISI: 000261329700006ScopusID: 2-s2.0-57349107952OAI: oai:DiVA.org:kth-18021DiVA: diva2:336066
QC 201005252010-08-052010-08-052012-01-23Bibliographically approved