Change search
ReferencesLink to record
Permanent link

Direct link
On bounded occurrence constraint satisfaction
KTH, Superseded Departments, Mathematics.ORCID iD: 0000-0002-5379-345X
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
Abstract [en]

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.
Keyword [en]
analysis of algorithms, computational complexity, approximation algorithms, approximation algorithms
URN: urn:nbn:se:kth:diva-19719ISI: 000086758900001OAI: diva2:338411
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Håstad, Johan
By organisation
In the same journal
Information Processing Letters

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: 29 hits
ReferencesLink to record
Permanent link

Direct link