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 |