A Geometric Approach to the Betweenness Problem

An input to the betweenness problem contains m constraints over n real variables. Each constraint consists of three variables, where one of the variables is specified to lie inside the interval defined by the other two. The order of the other two variables (which one is the largest and which one is the smallest) is not specified. This problem comes up in questions related to physical mapping in computational molecular biology. In 1979, Opatrny has shown that the problem of deciding whether the $n$ variables can be totally ordered while satisfying the $m$ betweenness constraints is NP-complete. Furthermore, the problem is MAX SNP complete. Therefore, there is some epsilon>0 such that finding a total order which satisfies at least m(1-epsilon) of the constraints (even if they are all satisfiable) is NP-- hard. It is easy to find an ordering of the variables which satisfies 1/3 of the m constraints (e.g. by choosing the ordering at random). In this work we present a polynomial time algorithm which either determines that there is no feasible solution, or finds a total order which satisfies at least 1/2 of the m constraints. Our algorithm translates the problem into a set of quadratic inequalities, and solves a semidefinite relaxation of them in R^n. The n solution points are then projected on a random line through the origin. Using simple geometric properties of the SDP solution, we prove the claimed performance guarantee.