A GEOMETRIC APPROACH TO BETWEENNESS

An input to the betweenness problem contains m constraints over n real variables (points). Each constraint consists of three points, where o ne of the points is specified to lie inside the interval defined by th e other two. The order of the other two points (i.e., 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 molecular biolog y. In 1979, Opatrny showed that the problem of deciding whether the n points can be totally ordered while satisfying the m betweenness const raints is NP-complete [SIAM J. Comput., 8 (1979), pp. 111-114]. Furthe rmore, the problem is MAX SNP complete, and for every alpha > 47/48 fi nding a total order that satisfies at least alpha of the m constraints is NP-hard (even if all the constraints are satisfiable). It is easy to find an ordering of the points that satisfies 1/3 of them constrain ts (e.g., by choosing the ordering at random). This paper presents a p olynomial time algorithm that either determines that there is no feasi ble solution or finds a total order that satisfies at least 1/2 of the m constraints. The algorithm translates the problem into a set of quad ratic inequalities and solves a semidefinite relaxation of them in R-n . The n solution points are then projected on a random line through th e origin. The claimed performance guarantee is shown using simple geom etric properties of the semidefinite programming (SDP) solution.