Learning Lines with Ordinal Constraints

We study the problem of finding a mapping f from a set of points into the real line, under ordinal triple constraints. An ordinal constraint for a triple of points (u,v,w) asserts that |f(u)-f(v)|<|f(u)-f(w)|. We present an approximation algorithm for the dense case of this problem. Given an instance that admits a solution that satisfies (1-varepsilon)-fraction of all constraints, our algorithm computes a solution that satisfies (1-O(varepsilon1/8))-fraction of all constraints, in time O(n7) + (1/varepsilon)^O(1/varepsilon1/8) n.