Change search
ReferencesLink to record
Permanent link

Direct link
Approximating MAX kCSP using random restrictions
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
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)
Abstract [en]

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.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-43971ISI: 000223565900014ScopusID: 2-s2.0-33645617671ISBN: 3-540-22894-2OAI: 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 20111024Available from: 2011-10-24 Created: 2011-10-19 Last updated: 2011-11-01Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Hast, Gustav
By organisation
Numerical Analysis and Computer Science, NADA
Computer Science

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

Total: 11 hits
ReferencesLink to record
Permanent link

Direct link