Learning Lines with Ordinal Constraints
This addresses a theoretical computational geometry problem with potential applications in ranking or ordering tasks, but it appears incremental as it builds on prior work in approximation algorithms for ordinal constraints.
The paper tackles the problem of mapping points to a real line under ordinal triple constraints, presenting an approximation algorithm that, given a solution satisfying a (1-ε)-fraction of constraints, computes one satisfying a (1-O(ε^{1/8}))-fraction in specified time.
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$.