%0 Journal Article
%T On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
%A Per Austrin
%A Rajsekar Manokaran
%A Cenny Wenner
%J Computer Science
%D 2013
%I arXiv
%X 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+\epsilon$ and $1/2+\epsilon$. 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 $\neq$ \NP.
%U http://arxiv.org/abs/1307.5090v1