2020/02/24 by Chubarian, Karine, Sidiropoulos, Anastasios
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2002.10039
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(c2), 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 outliers. Specifically, we say that a metric space (X,ρ) admits a (k,c)-embedding if there exists K⊂ X, with |K|=k, such that (X∖ K, ρ) admits an embedding into the line with distortion at most c. Given k≥ 0, and a metric space that admits a (k,c)-embedding, for some c≥ 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.