Revised: May 18, 2014
Published: June 18, 2015
Abstract: [Plain Text Version]
We show improved $\mathsf{NP}$-hardness of approximating Ordering-Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove $\mathsf{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 $\mathsf{P} \neq \mathsf{NP}$.
An extended abstract of this paper appeared in the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013).