摘要：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²), where c denotes the optimal distortion [BÄfdoiu et al. 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 âS, 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 (poly(k, c, log n), poly(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.
