Theory of Computing
-------------------
Title : On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
Authors : Per Austrin, Rajsekar Manokaran, and Cenny Wenner
Volume : 11
Number : 10
Pages : 257-283
URL : http://www.theoryofcomputing.org/articles/v011a010
Abstract
--------
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 NP-hard
approximation factors of ${14}/{15}+\varepsilon$ and
${1}/{2}+\varepsilon$. 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-$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 \neq NP.
An [extended abstract](http://dx.doi.org/10.1007/978-3-642-40328-6_3)
of this paper appeared in the 15th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX 2013)