Learning Lines with Ordinal Constraints

Abstract

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-\epsilon )$-fraction of all constraints, our algorithm computes a solution that satisfies $(1-O({\epsilon }^{1/8}))$-fraction of all constraints, in time $O(n^7)+(1/\epsilon {)}^{O(1/{\epsilon }^{1/8})}n$.