On bounded occurrence constraint satisfaction
2000 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 74, no 02-jan, 1-6 p.Article in journal (Refereed) Published
An approximation algorithm for a constraint satisfaction problem is said to be nontrivial if its performance ratio is strictly superior to the expected performance of the algorithm which simply chooses a random assignment. We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm.
Place, publisher, year, edition, pages
2000. Vol. 74, no 02-jan, 1-6 p.
analysis of algorithms, computational complexity, approximation algorithms, approximation algorithms
IdentifiersURN: urn:nbn:se:kth:diva-19719ISI: 000086758900001OAI: oai:DiVA.org:kth-19719DiVA: diva2:338411
QC 201005252010-08-102010-08-10Bibliographically approved