On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
2014 (English)In: Theory of Computing, ISSN 1557-2862Article in journal (Refereed) Accepted
We show improved NP-hardness of approximating Ordering Constraint Satis-faction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NP-hard approximation factors of 14/15+ε and 1/2+ε. When it is hard to approximate an OCSP by a constant better than takinga uniformly-at-random ordering, then the OCSP is said to be approximation resistant. We show that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs only to P != NP.
Place, publisher, year, edition, pages
Theory of Computing , 2014.
Constraint Satisfaction, CSPs, Approximation Resistance, Orderings, Acyclic Subgraph, Minimum Feedback Arc Set, Betweenness
Research subject Computer Science
IdentifiersURN: urn:nbn:se:su:diva-107683OAI: oai:DiVA.org:su-107683DiVA: diva2:749393
FunderEU, European Research Council, 226203Swedish Research Council, 621-2012-4546
Unpublished final version.
Open-access online journal. No page numbers or printing location.2014-09-242014-09-242014-09-25