论文标题
将Bi-Lipschitz离群值嵌入到线上
Computing Bi-Lipschitz Outlier Embeddings into the Line
论文作者
论文摘要
将图形度量嵌入BI-Lipschitz嵌入到线路中的问题的问题引起了很多关注。最著名的近似算法计算了用失真$ o（c^2）$的嵌入，其中$ c $表示最佳失真[bădoiu\ etal〜2005]。我们提出了一种双标准近似算法，该算法将上述结果扩展到\ emph {outliers}的设置。 具体而言，我们说的是，公制空间$（x，ρ）$承认$（k，c）$ - 如果存在$ k \ subset x $，则嵌入$ | k | = k $，因此$（x \ setMinus k，ρ）$承认最多损坏了损坏的嵌入方式。给定的$ k \ geq 0 $，以及一个承认$（k，c）$的公制空间 - 嵌入，对于某些$ c \ geq 1 $，我们的算法计算一个$（{\ Mathsf p} {\ Mathsf P} {\ Mathsf O} P} {\ Mathsf O} {\ Mathsf L} {\ Mathsf y}（c））$ - 在多项式时间内嵌入。这是离群Bi-Lipschitz嵌入的第一个算法结果。在我们的工作之前，可比较的离群值嵌入，仅因添加剂失真而知。
The problem of computing a bi-Lipschitz embedding of a graphical metric into the line with minimum distortion has received a lot of attention. The best-known approximation algorithm computes an embedding with distortion $O(c^2)$, where $c$ denotes the optimal distortion [Bădoiu \etal~2005]. We present a bi-criteria approximation algorithm that extends the above results to the setting of \emph{outliers}. Specifically, we say that a metric space $(X,ρ)$ admits a $(k,c)$-embedding if there exists $K\subset X$, with $|K|=k$, such that $(X\setminus K, ρ)$ admits an embedding into the line with distortion at most $c$. Given $k\geq 0$, and a metric space that admits a $(k,c)$-embedding, for some $c\geq 1$, our algorithm computes a $({\mathsf p}{\mathsf o}{\mathsf l}{\mathsf y}(k, c, \log n), {\mathsf p}{\mathsf o}{\mathsf l}{\mathsf y}(c))$-embedding in polynomial time. This is the first algorithmic result for outlier bi-Lipschitz embeddings. Prior to our work, comparable outlier embeddings where known only for the case of additive distortion.
