On average distortion of embedding metrics into the line and into L 1

DOI10.1145/780542.780609zbMath1192.90237OpenAlexW2093171982MaRDI QIDQ3581251

Yuri Rabinovich

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780609

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Algorithms in computer science (68W99)

Related Items (9)

A note on multiflows and treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Volume in general metric spaces ⋮ Advances in metric embedding theory ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Metric structures in \(L_1\): dimension, snowflakes, and average distortion

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