LIPIcs.SWAT.2020.32.pdf
- Filesize: 0.55 MB
- 13 pages
Document
Online Embedding of Metrics
Authors
-
Part of:
Volume:
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-12
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.SWAT.2020.32
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.
Subject Classification
ACM Subject Classification
- Networks → Network algorithms
Keywords
- Metric spaces
- online embedding
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh S. Vempala. Local versus global properties of metric spaces. SIAM J. Comput., 41(1):250-271, 2012. URL: https://doi.org/10.1137/090780304.
- Yair Bartal. On approximating arbitrary metrices by tree metrics. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 161-168. ACM, 1998. URL: https://doi.org/10.1145/276698.276725.
- Yair Bartal, Nova Fandina, and Seeun William Umboh. Online probabilistic metric embedding: A general framework for bypassing inherent bounds. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1538-1557, 2020. URL: https://doi.org/10.1137/1.9781611975994.95.
- Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel J. Math., 52:46-52, 1985. URL: https://doi.org/10.1007/BF02776078.
- Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. Theor. Comput. Sci., 697:1-36, 2017. URL: https://doi.org/10.1016/j.tcs.2017.06.021.
- Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, and Anastasios Zouzias. Online embeddings. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 246-259. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_19.
-
William B. Johnson and Joram Lindenstrauss. Extensions of 1-lipschitz mappings into a hilbert space. Contemporary mathematics, 26:198-206, 1984.
- Ilan Newman and Yuri Rabinovich. A lower bound on the distortion of embedding planar metrics into euclidean space. Discrete Comput. Geom., 29:77-81, 2002. URL: https://doi.org/10.1007/s00454-002-2813-5.