Simple Linear Time Approximation Algorithm for Betweenness

In this technical report, we present a simple combinatorial algorithm for the Betweenness problem. In the Betweenness problem, we are given a set of vertices and betweenness constraints. Each betweenness constraint of the form u => (v, w) requires that the vertex u lies between vertices v and w. Our goal is to find an ordering of vertices that maximizes the number of satisfied constraint. In 1995, Chor and Sudan constructed an SDP algorithm that satisfies half of all constraints if the instance is (completely) satisfiable. We present a simple linear time algorithm with the same approximation guarantee.