Distortion lower bounds for line embeddings

DOI10.1016/j.ipl.2008.05.003zbMath1191.68452OpenAlexW2091396615MaRDI QIDQ975439

Charalampos Papamanthou, Claire Mathieu

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.05.003

zbMATH Keywords

combinatorial problemstheory of computation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items

Optimal distortion embedding of complete binary trees into lines

Cites Work

• Unnamed Item
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Graphs with small bandwidth and cutwidth
• Optimal embedding of complete binary trees into lines and grids
• The Euclidean distortion of complete binary trees
• Embedding tree metrics into low dimensional Euclidean spaces
• Low-distortion embeddings of general metrics into the line
• Low-Distortion Embeddings of Trees
• Improved algorithms for optimal embeddings