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$.
