On the np-hardness of max-not-2
2014 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 43, no 1, 179-193 p.Article in journal (Refereed) Published
We prove that, for any epsilon > 0, given a satisfiable instance of Max-NTW (Not-2), it is NP-hard to find an assignment that satisfies a fraction 5/8 + epsilon of the constraints. This, up to the existence of epsilon, 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 complete our understanding of arity three maximum constraint satisfaction problems with regards to approximation resistance.
Place, publisher, year, edition, pages
2014. Vol. 43, no 1, 179-193 p.
constraint satisfaction, approximation resistance, probabilistically checkable proofs
Computer Science Mathematics
IdentifiersURN: urn:nbn:se:kth:diva-144972DOI: 10.1137/120882718ISI: 000333538300009ScopusID: 2-s2.0-84896917344OAI: oai:DiVA.org:kth-144972DiVA: diva2:716096
FunderEU, European Research Council, 226203
QC 201405082014-05-082014-05-052014-05-08Bibliographically approved