2026-09-10T09:44:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27734 2026-09-09T12:19:35Z ddc:004 open_access

Bi-Lipschitz Extensions and Outlier Embeddings into Trees Chawla, Shuchi Filtser, Arnold Sheridan, Kristin Trachtenberg, Yonatan metric embeddings hierarchically separated trees outliers We develop low distortion embeddings with outliers from arbitrary metrics into hierarchically separated trees (HSTs). In particular, we develop an efficient algorithm that for any ε > 0, given an input metric (X,d), and a probabilistic embedding of all but k points from X into HSTs with distortion c, samples from a probabilistic embedding of all but O((k/ε)log k) points into HSTs that achieves distortion at most (32+ε)c. Our results are based on two key technical components. First, we extend an algorithm of Munagala et al. [Munagala et al., 2023] for minimizing the distortion of embeddings without outliers into HSTs to the setting with outliers. We combine this with new results on bi-Lipschitz extensions into trees and 𝓁₁ space. In particular, we show that any probabilistic embedding into HSTs can be extended to k additional points with only a factor O(log k) of additional distortion. This bi-Lipschitz extension result utilizes a new probabilistic partitioning scheme that we call onion partitioning. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuchi Chawla and Arnold Filtser and Kristin Sheridan and Yonatan Trachtenberg 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.17 urn:nbn:de:0030-drops-277346 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode