  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.
