Sparsest cut and L1 metric embeddings
Kent Quanrud · 79:50
Any finite metric can be embedded into \(\ell1\) with \(O(\log n)\) distortion (Bourgain / Fréchet embeddings), and that is exactly the missing piece that turns a metric LP for sparsest cut into an \(O(\log n)\)-appro...