Krzysztof Onak: updated header

2013-03-07T01:56:09Z

updated header

Krzysztof Onak: Created page with "{{Header |title=Sketching Earth Mover Distance |source=bertinoro11 |who=Piotr Indyk }} For any two subsets $A,B$ of the planar grid $[n]^2$, $|A|=|B|$, define \[ \operatornam..."

2012-12-06T23:37:48Z

Created page with "{{Header |title=Sketching Earth Mover Distance |source=bertinoro11 |who=Piotr Indyk }} For any two subsets $A,B$ of the planar grid $[n]^2$, $|A|=|B|$, define \[ \operatornam..."

New page

{{Header
|title=Sketching Earth Mover Distance
|source=bertinoro11
|who=Piotr Indyk
}}
For any two subsets $A,B$ of the planar grid $[n]^2$, $|A|=|B|$, define
\[ \operatorname{EMD}(A,B)=\min_{\pi: A \to B} \sum_{a \in A} \|a-\pi(a)\|_1, \]
where $\pi$ ranges over one-to-one mapping from $A$ to $B$.

'''Question:''' What is the sketching complexity of $c$-approximating EMD? That is, consider a distribution over mappings $L_c$ that maps subset of $[n]^2$ to $\{0,1\}^s$, such that for any sets $A,B$ with $|A|=|B|$, given $L_c(A), L_c(B)$, one can estimate $\operatorname{EMD}(A,B)$ up to a factor of $c$, with probability $\ge 2/3$. Is it possible to construct such a distribution for constant $c$ and $s=\operatorname{polylog} n$?

'''Background:''' It is known that one can achieve $s=O(\log n)$ for $c=O(\log n)$ by embedding EMD into $\ell_1$ {{cite|IndykT-03|Charikar-02}}, and $s=n^{O(1/c)} \operatorname{polylog} n$ for any $c \ge 1$ {{cite|AndoniDIW-09}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Piotr Indyk

Open Problems:49 - Revision history

Krzysztof Onak: updated header

Krzysztof Onak: Created page with "{{Header |title=Sketching Earth Mover Distance |source=bertinoro11 |who=Piotr Indyk }} For any two subsets $A,B$ of the planar grid $[n]^2$, $|A|=|B|$, define \[ \operatornam..."