Planar Earthmover is not in $L_1$

Simple item page
dc.creatorNaor, Assaf
dc.creatorSchechtman, Gideon
dc.date2005-09-26
dc.date.accessioned2026-07-07T06:41:57Z
dc.date.available2026-07-07T06:41:57Z
dc.descriptionWe show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid $\{0,1,...,n\}^2\subseteq \R^2$ incurs distortion $Ω(\sqrt{\log n})$. We also use Fourier analytic techniques to construct a simple $L_1$ embedding of this space which has distortion $O(\log n)$.
dc.identifierhttps://arxiv.org/abs/cs/0509074
dc.identifierhttp://arxiv.org/abs/cs/0509074
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/101861
dc.subjectComputational Geometry
dc.subjectFunctional Analysis
dc.titlePlanar Earthmover is not in $L_1$
dc.typetext

Files

Collections

arXiv