A geometric approach to betweenness

Abstract

An input to the betweenness problem contains m constraints over n real variables (points). Each constraint consists of three points, where one of the points is specified to lie inside the interval denned by the 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 biology. In 1979, Opatrny showed that the problem of deciding whether the n points can be totally ordered while satisfying the m betweenness constraints is NP-complete [SIAM J. Comput, 8 (1979), pp. 111-114]. Furthermore, the problem is MAX SNP complete, and for every α > 47/48 finding a total order that satisfies at least α 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 the m constraints (e.g., by choosing the ordering at random). This paper presents a polynomial time algorithm that either determines that there is no feasible 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 quadratic inequalities and solves a semidefinite relaxation of them in Rn. The n solution points are then projected on a random line through the origin. The claimed performance guarantee is shown using simple geometric properties of the semidefinite programming (SDP) solution.