On average distortion of embedding metrics into the line

DOI10.1007/s00454-007-9047-5zbMath1158.68050OpenAlexW2012737834MaRDI QIDQ938313

Yuri Rabinovich

Publication date: 19 August 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-007-9047-5

zbMATH Keywords

Average distortionMetric embeddings

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (6)

Metric Embedding via Shortest Path Decompositions ⋮ An introduction to the Ribe program ⋮ Comparison of Metric Spectral Gaps ⋮ Near-Optimal Separators in String Graphs ⋮ An average John theorem ⋮ Multicommodity flows and cuts in polymatroidal networks

Cites Work

• Unnamed Item
• Unnamed Item
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• On Lipschitz embedding of finite metric spaces in Hilbert space
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• The geometry of graphs and some of its algorithmic applications
• Algorithms on Strings, Trees and Sequences
• Excluded minors, network decomposition, and multicommodity flow
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Expander flows, geometric embeddings and graph partitioning
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• A tight bound on approximating arbitrary metrics by tree metrics
• On dominated \(\ell_1\) metrics

This page was built for publication: On average distortion of embedding metrics into the line