Metric Embeddings with Relaxed Guarantees
From MaRDI portal
Publication:3654378
DOI10.1137/060670511zbMath1191.68348MaRDI 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
metric spaces; randomized algorithms; metric embeddings; low-distortion embeddings; metric decompositions
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
51F99: Metric geometry
54C25: Embedding
68W20: Randomized algorithms
Related Items
Unnamed Item, Advances in metric embedding theory, Approximating snowflake metrics by trees, Metric violation distance: hardness and approximation, Information Preserving Dimensionality Reduction