Embedding approximately low-dimensional ${\ell }_2^2$ metrics into ${\ell }_1$

Amit Deshpande, Prahladh Harsha, Rakesh Venkat

Goemans showed that any $n$ points $x_1,\dots x_n$ in $d$-dimensions satisfying ${\ell }_2^2$ triangle inequalities can be embedded into ${\ell }_1$, with worst-case distortion at mo…