Planar earthmover is not in L1

Assaf Naor, Gideon Schechtman

Research output: Contribution to journalArticle

Abstract

We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2 ⊆ ℝ2 incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O(log n).

Original languageEnglish (US)
Pages (from-to)804-826
Number of pages23
JournalSIAM Journal on Computing
Volume37
Issue number3
DOIs
StatePublished - 2007

Keywords

  • Earthmover metric
  • Metric embeddings
  • Nearest neighbor search

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Planar earthmover is not in L<sub>1</sub>'. Together they form a unique fingerprint.

  • Cite this