DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.39

Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces

Authors: Noam Licht, Ilan Newman, and Yuri Rabinovich

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We study online embeddings of metric spaces into Euclidean spaces of a constant dimension d > 1, against an adaptive adversary. While the case of d = 1 is well understood, for higher dimensions little is known. In particular, even for d = 2 it remains unknown whether the worst-case distortion grows exponentially with the number of exposed points, as it does in the case for the line, or whether it is polynomial, as in the case for unbounded d. Our first result is about fixed solid graphs, i.e., K₅, whose edges are solid intervals, equipped with the shortest-path metric. We show that if the input points arrive from such a metric space, they can indeed be online-embedded into ℝ² with a polynomial distortion. This refutes the previously believed conjecture that the topological non-embeddability of K₅ into the plane could be exploited for establishing exponential lower bounds. The second results is about online embeddings of tree metrics of a certain type, including, e.g., ultrametrics and HST’s. Somewhat surprisingly, we show that for metrics from this class the worst-case online embedding into ℝ^d is not much worse that the offline embedding, both being n^Θ(1/d), and this holds even when d = Θ(log n). This is in a stark contrast to the more common situation where the online-offline gap is typically huge, and even exponential. This result allows us to transfer results about probabilistic embeddings of metrics into HST’s to low-dimensional Euclidean spaces, in an almost optimal possible manner.

Cite as

Noam Licht, Ilan Newman, and Yuri Rabinovich. Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{licht_et_al:LIPIcs.ESA.2026.39,
  author =	{Licht, Noam and Newman, Ilan and Rabinovich, Yuri},
  title =	{{Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.39},
  URN =		{urn:nbn:de:0030-drops-271750},
  doi =		{10.4230/LIPIcs.ESA.2026.39},
  annote =	{Keywords: online embedding, metric embedding, online algorithms, design of algorithms}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2020.32

Online Embedding of Metrics

Authors: Ilan Newman and Yuri Rabinovich

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract

We study deterministic online embeddings of metric spaces into normed spaces of various dimensions and into trees. We establish some upper and lower bounds on the distortion of such embedding, and pose some challenging open questions.

Cite as

Ilan Newman and Yuri Rabinovich. Online Embedding of Metrics. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{newman_et_al:LIPIcs.SWAT.2020.32,
  author =	{Newman, Ilan and Rabinovich, Yuri},
  title =	{{Online Embedding of Metrics}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.32},
  URN =		{urn:nbn:de:0030-drops-122792},
  doi =		{10.4230/LIPIcs.SWAT.2020.32},
  annote =	{Keywords: Metric spaces, online embedding}
}

Search Results

Documents authored by Rabinovich, Yuri

Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces

Abstract

Cite as

Online Embedding of Metrics

Abstract

Cite as

Thanks for your feedback!

Could not send message