Computing Bi-Lipschitz Outlier Embeddings into the Line

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 [Bu{a}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,rho)$ admits a $(k,c)$-embedding if there exists $Ksubset X$, with $|K|=k$, such that $(Xsetminus K, rho)$ admits an embedding into the line with distortion at most $c$. Given $kgeq 0$, and a metric space that admits a $(k,c)$-embedding, for some $cgeq 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.