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}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2026.23

Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes

Authors: Shuchi Chawla and Kristin Sheridan

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract

We consider the problem of finding the value of a maximum flow over time in a network with uniform edge lengths where the edge capacities change over time. We assume that the capacity of every edge in the network is a piecewise constant function and parameterize the running time of our algorithm by the total number of pieces in the capacity functions across all edges, denoted μ. The key technical component in our approach is a condensed version of a Time Expanded Network (that we call a cTEN) whose classical max flow value is the same as the max flow over time on the original network. We show that a graph with n nodes, m edges, and μ capacity changes, admits a cTEN with O(n²μ) nodes and O(μ mn) edges. This implies that the problem can be solved in O(μ²n³m) time using the combinatorial max flow algorithm of Orlin [Orlin, 2013], or in O(μ^(1+o(1)) (nm)^(1+o(1)) log (nUT)) time using the algorithm of Chen et al. [Chen et al., 2022], where U is the maximum capacity of any edge and T is the time horizon. When μ >> m,n, this is faster than previously known algorithms for this problem.

Cite as

Shuchi Chawla and Kristin Sheridan. Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 23:1-23:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.SAND.2026.23,
  author =	{Chawla, Shuchi and Sheridan, Kristin},
  title =	{{Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{23:1--23:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.23},
  URN =		{urn:nbn:de:0030-drops-262578},
  doi =		{10.4230/LIPIcs.SAND.2026.23},
  annote =	{Keywords: maximum flow, dynamic flows, flows over time}
}

Search Results

Documents authored by Sheridan, Kristin

Bi-Lipschitz Extensions and Outlier Embeddings into Trees

Abstract

Cite as

Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes

Abstract

Cite as

Thanks for your feedback!

Could not send message