Near-optimal distortion bounds for embedding doubling spaces into L 1

DOI10.1145/1993636.1993737zbMath1288.90079OpenAlexW2041493135MaRDI QIDQ5419147

James R. Lee, Anastasios Sidiropoulos

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

integrality gapsparsest cutmetric embeddings

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (6)

Vertical perimeter versus horizontal perimeter ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Corrigendum: Metric Embedding via Shortest Path Decompositions ⋮ Heat flow and quantitative differentiation ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Low dimensional embeddings of doubling metrics

This page was built for publication: Near-optimal distortion bounds for embedding doubling spaces into L ₁