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 : https://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)