License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.32
URN: urn:nbn:de:0030-drops-122792
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12279/
Go to the corresponding LIPIcs Volume Portal

Newman, Ilan ; Rabinovich, Yuri

Online Embedding of Metrics

pdf-format:
LIPIcs-SWAT-2020-32.pdf (0.6 MB)

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
Collection: 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