摘要：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-ε)-fraction of all constraints, our algorithm computes a solution that satisfies (1-O(ε^{1/8}))-fraction of all constraints, in time O(nâ·) + (1/ε)^{O(1/ε^{1/8})} n.
关键词：metric learning; embedding into the line; ordinal constraints; approximation algorithms
