论文标题
学习线与序数约束
Learning Lines with Ordinal Constraints
论文作者
论文摘要
我们研究了在序数三限制下从一组点找到映射$ f $的问题。点三重的序数约束$（u，v，w）$断言$ | f（u）-f（v）| <| f（u）-f（w）| $。我们为该问题的致密情况提供了一种近似算法。给定一个实例，该实例承认满足$（1- \ varepsilon）$的解决方案 - 所有约束的分数，我们的算法计算一个满足$（1-o（\ varepsilon^{1/8}））$的解决方案 - （1/\ varepsilon）^{o（1/\ varepsilon^{1/8}）} n $。
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$.
