Change search
ReferencesLink to record
Permanent link

Direct link
Beating a random assignment
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2005 (English)In: APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES / [ed] Chekuri, C; Jansen, K; Rolim, JDP; Trevisan, L, 2005, Vol. 3624, 134-145 p.Conference paper (Refereed)
Abstract [en]

MAX CSP(P) is the problem of maximizing the weight of satisfied constraints, where each constraint acts over a k-tuple of literals and is evaluated using the predicate P. The approximation ratio of a random assignment is equal to the fraction of satisfying inputs to P. If it is NP-hard to achieve a better approximation ratio for MAX CSP(P), then we say that P is approximation resistant. Our goal is to characterize which predicates that have this property. A general approximation algorithm for MAX CSP(P) is introduced. For a multitude of different P, it is shown that the algorithm beats the random assignment algorithm, thus implying that P is not approximation resistant. In particular, over 2/3 of the predicates on four binary inputs are proved not to be approximation resistant, as well as all predicates on 2s binary inputs, that have at most 2s + I accepting inputs. We also prove a large number of predicates to be approximation resistant. In particular, all predicates of arity 2s + s(2) with less than 2(s2) nonaccepting inputs axe proved to be approximation resistant, as well as almost 1/5 of the predicates on four binary inputs.

Place, publisher, year, edition, pages
2005. Vol. 3624, 134-145 p.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-42724ISI: 000232240900012ScopusID: 2-s2.0-26944440861ISBN: 3-540-28239-4OAI: diva2:448083
8th International Workshop on Approxination Algorithms for Combinatorial Optimization Problems/9th International Workshop on Randomization and Computation Location: Berkeley, CA Date: AUG 22-24, 2005
QC 20111014Available from: 2011-10-14 Created: 2011-10-12 Last updated: 2011-10-14Bibliographically 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 and Information 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: 7 hits
ReferencesLink to record
Permanent link

Direct link