$L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids

Chris Gartland, Mikhail Ostrovskii, Yuval Rabani +1

We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\{1,\dots m{\}}^d$ is $\Omega (\log N)$, wher…