2026-08-07T03:51:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12639 2024-03-06T10:51:19Z ddc:004 open_access

Computing Bi-Lipschitz Outlier Embeddings into the Line Chubarian, Karine Sidiropoulos, Anastasios metric embeddings outliers distortion approximation algorithms 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ădoiu 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 ⊂ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karine Chubarian and Anastasios Sidiropoulos 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.36 urn:nbn:de:0030-drops-126398 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.36 eng https://creativecommons.org/licenses/by/3.0/legalcode