Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces

Yuval Rabani, Rakesh Venkat

We consider the problem of embedding a finite set of points $\{x_1,\dots ,x_n\}\in {\mathbb{R}}^d$ that satisfy ${\ell }_2^2$ triangle inequalities into ${\ell }_1$, when the points are…