Improved lower bounds for embeddings into L1
From MaRDI portal
Publication:3583421
DOI10.1145/1109557.1109669zbMath1192.90178MaRDI 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
90C27: Combinatorial optimization
54E35: Metric spaces, metrizability
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Euclidean distortion and the sparsest cut, Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\), Real-valued embeddings and sketches for fast distance and similarity estimation, On a class of metrics related to graph layout problems, Approximating tree edit distance through string edit distance, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas