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(varepsilon^{1/8}))$-fraction of all constraints, in time $O(n^7) + (1/varepsilon)^{O(1/varepsilon^{1/8})} n$.