On the NP-hardness of approximating ordering constraint satisfaction problems
2013 (English)In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, Springer, 2013, 26-41 p.Conference paper (Refereed)
We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of 14/15 + ε and 1/2 + ε. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove 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 subject only to P ≠ NP. Our reductions from Label Cover differ from previous works in two ways. First, we establish a somewhat general bucketing lemma permitting us to reduce the analysis of ordering predicates to that of classical predicates. Second, instead of "folding", which is not available for ordering predicates, we employ permuted instantiations of the predicates to limit the value of poorly correlated strategies.
Place, publisher, year, edition, pages
Springer, 2013. 26-41 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 8096 LNCS
Acyclic subgraph, Betweenness, Inapproximability, IS approximation, NP-hardness, Ordering constraints, Two ways
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-136123DOI: 10.1007/978-3-642-40328-6_3ScopusID: 2-s2.0-84885206841ISBN: 978-364240327-9OAI: oai:DiVA.org:kth-136123DiVA: diva2:675596
16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013; Berkeley, CA; United States; 21 August 2013 through 23 August 2013
QC 201312042013-12-042013-12-032014-09-29Bibliographically approved