Header menu link for other important links
On the NP-hardness of approximating ordering-constraint satisfaction problems
P. Austrin, , C. Wenner
Published in University of Chicago, Department of Computer Science
Volume: 11
Pages: 257 - 283
We show improved NPNP-hardness of approximating Ordering-Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NPNP-hard approximation factors of 14/15+ε14/15+ε and 1/2+ε1/2+ε. When it is hard to approximate an OCSP by a constant better than taking a 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-mm 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. © 2015 Per Austrin, Rajsekar Manokaran, and Cenny Wenner.
About the journal
JournalTheory of Computing
PublisherUniversity of Chicago, Department of Computer Science