Distortion lower bounds for line embeddings

DOI10.1016/J.IPL.2008.05.003MaRDI QIDQ975439zbMATH OpenOpenAlexFDO

Authors Claire Mathieu, Charalampos Papamanthou

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

theory of computationcombinatorial problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Recommendations

• Low-distortion embeddings of general metrics into the line
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• On average distortion of embedding metrics into the line and into \(l_1\)
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• STACS 2004

Cites work

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

Cited in

(6)

• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• Near-optimal distortion bounds for embedding doubling spaces into L ₁
• On average distortion of embedding metrics into the line
• Optimal distortion embedding of complete binary trees into lines
• Tight distortion bounds for distributed metric voting on a line
• Low-distortion embeddings of general metrics into the line

This page was built for publication: Distortion lower bounds for line embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975439)