Approximating MAX kCSP using random restrictions
2004 (English)In: APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, PROCEEDINGS / [ed] Jansen, K; Khanna, S; Rolim, JDP; Ron, D, BERLIN: SPRINGER , 2004, Vol. 3122, 151-162 p.Conference paper (Refereed)
In this paper we study the approximability of the maximization version of constraint satisfaction problems. We provide two probabilistic approximation algorithms for MAX kCONJSAT which is the problem to satisfy as many conjunctions, each of size at most k, as possible. As observed by Trevisan, this leads to approximation algorithms with the same approximation ratio for the more general problem MAX kCSP, where instead of conjunctions arbitrary k-ary constraints are imposed. The first algorithm achieves an approximation ratio of 2(1.40-k). The second algorithm achieves a slightly better approximation ratio of 2(1.54-k), but the ratio is shown using computational evidence. These ratios should be compared with the previous best algorithm, due to Trevisan, that achieves an approximation ratio of 2(1-k). Both the new algorithms use a combination of random restrictions, a method which have been used in circuit complexity, and traditional semidefinite relaxation methods. A consequence of these algorithms is that some complexity classes described by probabilistical checkable proofs can be characterized as subsets of P. Our result in this paper implies that PCPc,s [log, k] subset of or equal to P for any c/s > 2(k-1.40), and we have computational evidence that if c/s > 2(k-1.54) this inclusion still holds.
Place, publisher, year, edition, pages
BERLIN: SPRINGER , 2004. Vol. 3122, 151-162 p.
, LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 3122
IdentifiersURN: urn:nbn:se:kth:diva-43971ISI: 000223565900014ScopusID: 2-s2.0-33645617671ISBN: 3-540-22894-2OAI: oai:DiVA.org:kth-43971DiVA: diva2:450912
7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/8th International Workshop on Randomization and Computation. Harvard Univ, Cambridge, MA. AUG 22-24, 2004
QC 201110242011-10-242011-10-192011-11-01Bibliographically approved