Simple linear time approximation algorithm for betweenness

We study the Betweenness problem. We are given a set of vertices and betweenness constraints. Each betweenness constraint of the form $x⇝\{y,z\}$ requires that vertex $x$ lies between vertices $y$ and $z$ . Our goal is to find a vertex ordering that maximizes the number of satisfied constraints. In 1995, Chor and Sudan designed an SDP algorithm that satisfies half of all constraints in a satisfiable instance. We present a simple combinatorial linear time algorithm with the same approximation guarantee.