Planar earthmover is not in L(1)

Assaf Naor; Gideon Schechtman

doi:10.1137/05064206x

Back

Journal article

Peer reviewed

Planar earthmover is not in L(1)

Assaf Naor and Gideon Schechtman

SIAM Journal on Computing, Vol.37(3), pp.804-826

2007

DOI: https://doi.org/10.1137/05064206x

Files and links (2)

url

https://doi.org/10.1137/05064206xView

Published (Version of record) Restricted

url

https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1137/05064206xView

Published (Version of record) Restricted

Abstract

We 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) subset of R(2) incurs distortion Omega (root log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O( log n).

Details

Title: Planar earthmover is not in L(1)
Creators: Assaf Naor (null)
Gideon Schechtman (null) - 972WIS_INST___84
Resource Type: Journal article
Publication Details: SIAM Journal on Computing, Vol.37(3), pp.804-826; 2007
Number of pages: 23
Language: English
DOI: https://doi.org/10.1137/05064206x
Record Identifier: 993263393003596

Metrics

9 Record Views