Every 2-CSP Allows Nontrivial Approximation
2005 (English)In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, 740-746 p.Conference paper (Refereed)
We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does provably better than picking a random assignment. To be more precise assume that each variable can take values in [d] and that each constraint rejects t out of the d2 possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, on expectation, within a factor (1- t/d2(1- c/d2 log d)) of optimal.
Place, publisher, year, edition, pages
2005. 740-746 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-63001DOI: 10.1145/1060590.1060700ScopusID: 2-s2.0-26944485593ISBN: 1-58113-960-8OAI: oai:DiVA.org:kth-63001DiVA: diva2:481480
the 37th Annual ACM Symposium on Theory of Computing
QC 201201232012-01-212012-01-212012-01-23Bibliographically approved