摘要：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}$
