Beating a random assignment
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)
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.
, LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 3624
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-42724ISI: 000232240900012ScopusID: 2-s2.0-26944440861ISBN: 3-540-28239-4OAI: oai:DiVA.org:kth-42724DiVA: 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 201110142011-10-142011-10-122011-10-14Bibliographically approved