Volume 11 (2015) Article 10 pp. 257-283
APPROX-RANDOM 2013 Special Issue
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
Received: September 11, 2013
Revised: May 18, 2014
Published: June 18, 2015
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}$.