Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
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, p. 134-145Conference paper, Published 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, p. 134-145
##### Series
LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 3624
##### National Category
Computer and Information Sciences
##### Identifiers
ISI: 000232240900012Scopus ID: 2-s2.0-26944440861ISBN: 3-540-28239-4 (print)OAI: oai:DiVA.org:kth-42724DiVA, id: diva2:448083
##### Conference
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
##### Note
QC 20111014Available from: 2011-10-14 Created: 2011-10-12 Last updated: 2018-01-12Bibliographically approved

#### Open Access in DiVA

No full text in DiVA
Scopus

#### Search in DiVA

Hast, Gustav
##### By organisation
Numerical Analysis and Computer Science, NADA
##### On the subject
Computer and Information Sciences

isbn
urn-nbn

#### Altmetric score

isbn
urn-nbn
Total: 22 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
v. 2.33.0
| | | |