Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Newman, Ilan; Rabinovich, Yuri https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-122792
URL:

;

Online Embedding of Metrics

pdf-format:


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.

BibTeX - Entry

@InProceedings{newman_et_al:LIPIcs:2020:12279,
  author =	{Ilan Newman and Yuri Rabinovich},
  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 =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12279},
  URN =		{urn:nbn:de:0030-drops-122792},
  doi =		{10.4230/LIPIcs.SWAT.2020.32},
  annote =	{Keywords: Metric spaces, online embedding}
}

Keywords: Metric spaces, online embedding
Seminar: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue date: 2020
Date of publication: 12.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI