DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.17

Bi-Lipschitz Extensions and Outlier Embeddings into Trees

Authors: Shuchi Chawla, Arnold Filtser, Kristin Sheridan, and Yonatan Trachtenberg

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Shuchi Chawla, Arnold Filtser, Kristin Sheridan, and Yonatan Trachtenberg. Bi-Lipschitz Extensions and Outlier Embeddings into Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.APPROX/RANDOM.2026.17,
  author =	{Chawla, Shuchi and Filtser, Arnold and Sheridan, Kristin and Trachtenberg, Yonatan},
  title =	{{Bi-Lipschitz Extensions and Outlier Embeddings into Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{17:1--17:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.17},
  URN =		{urn:nbn:de:0030-drops-277346},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.17},
  annote =	{Keywords: metric embeddings, hierarchically separated trees, outliers}
}

Search Results

Documents authored by Trachtenberg, Yonatan

Bi-Lipschitz Extensions and Outlier Embeddings into Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message