Change search
CiteExportLink to record
Permanent link

Direct link
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
On the NP-hardness of Max-Not-2
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2012 (English)In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag , 2012, 170-181 p.Conference paper, Published paper (Refereed)
Abstract [en]

We prove that, for any ε > 0, it is NP-hard to, given a satisfiable instance of Max-NTW (Not-2), find an assignment that satisfies a fraction 5/8 + ε of the constraints. This, up to the existence of ε, matches the approximation ratio obtained by the trivial algorithm that just picks an assignment at random and thus the result is tight. Said equivalently the result proves that Max-NTW is approximation resistant on satisfiable instances and this makes our understanding of arity three Max-CSPs with regards to approximation resistance complete.

Place, publisher, year, edition, pages
Springer-Verlag , 2012. 170-181 p.
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7408 LNCS
Keyword [en]
Approximation ratios, IS approximation, NP-hard, NP-hardness, Combinatorial optimization, Approximation algorithms
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-104872DOI: 10.1007/978-3-642-32512-0_15Scopus ID: 2-s2.0-84865289211ISBN: 978-364232511-3 (print)OAI: oai:DiVA.org:kth-104872DiVA: diva2:567830
Conference
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012, 15 August 2012 through 17 August 2012, Cambridge, MA
Note

QC 20121114

Available from: 2012-11-14 Created: 2012-11-14 Last updated: 2012-11-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
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