Metric Embeddings with Relaxed Guarantees

DOI10.1137/060670511zbMath1191.68348OpenAlexW2163217488MaRDI QIDQ3654378

T.-H. Hubert Chan, Aleksandrs Slivkins, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060670511

zbMATH Keywords

metric spacesrandomized algorithmsmetric embeddingslow-distortion embeddingsmetric decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Metric geometry (51F99) Embedding (54C25) Randomized algorithms (68W20)

Related Items (5)

Metric violation distance: hardness and approximation ⋮ Advances in metric embedding theory ⋮ Approximating snowflake metrics by trees ⋮ Information Preserving Dimensionality Reduction ⋮ Unnamed Item

This page was built for publication: Metric Embeddings with Relaxed Guarantees