Change search
ReferencesLink to record
Permanent link

Direct link
Some optimal inapproximability results
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2001 (English)In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 48, no 4, 798-859 p.Article in journal (Refereed) Published
Abstract [en]

We prove optimal, up to an arbitrary epsilon > 0, inapproximability results for Max-Ek-Sat for k greater than or equal to 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.

Place, publisher, year, edition, pages
2001. Vol. 48, no 4, 798-859 p.
Keyword [en]
theory, inapproximability, linear equations, max-sat, NP-hard optimization problems, probabilistically checkable proofs, approximation algorithms, vertex cover, approximability, complexity, hardness, proofs, set, np
URN: urn:nbn:se:kth:diva-21231ISI: 000173093400009OAI: diva2:339929
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
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of the ACM

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

Direct link