Simple linear time approximation algorithm for betweenness, Microsoft Research

In this technical report, we present a simple combinatorial algo-rithm for the Betweenness problem. In the Betweenness problem, we are given a set of vertices and betweenness constraints. Each between-ness 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 [2] constructed an SDP algorithm that satisfies half of all con-straints if the instance is (completely) satisfiable. We present a simple linear time algorithm with the same approximation guarantee.