Online Embedding of Metrics

Authors Ilan Newman, Yuri Rabinovich



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.32.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Ilan Newman
  • Department of Computer Science, University of Haifa, Israel
Yuri Rabinovich
  • Department of Computer Science, University of Haifa, Israel

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. William B. Johnson and Joram Lindenstrauss. Extensions of 1-lipschitz mappings into a hilbert space. Contemporary mathematics, 26:198-206, 1984. Google Scholar
  8. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail