Improved lower bounds for embeddings into L1

DOI10.1145/1109557.1109669zbMath1192.90178OpenAlexW4239545791MaRDI QIDQ3583421

Yuval Rabani, Robert Krauthgamer

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Metric spaces, metrizability (54E35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Approximating tree edit distance through string edit distance ⋮ On a class of metrics related to graph layout problems ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) ⋮ Unnamed Item ⋮ Euclidean distortion and the sparsest cut ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

This page was built for publication: Improved lower bounds for embeddings into L₁