Open Problems:7 - Revision history

128.30.9.27 at 21:26, 11 November 2014

2014-11-11T21:26:09Z

Krzysztof Onak at 01:39, 7 March 2013

2013-03-07T01:39:02Z

Krzysztof Onak at 05:00, 16 November 2012

2012-11-16T05:00:03Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 7: Estimating Earth-Mover Distance}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = [[Workshops:Kanpur_2006|Kanpur 2006]..."

2012-10-01T09:33:41Z

Created page with "{{DISPLAYTITLE:Problem 7: Estimating Earth-Mover Distance}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = [[Workshops:Kanpur_2006|Kanpur 2006]..."

New page

{{DISPLAYTITLE:Problem 7: Estimating Earth-Mover Distance}}
{{Infobox
|label1 = Proposed by
|data1 = Piotr Indyk
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/7
}}
Consider a stream of red points $R$ and blue points $B$ from a 2-dimensional
grid $[\Delta]^2$, in an arbitrary order. We assume $|R|=|B|=n$.
The Earth-Mover Distance (EMD) between $R$ and $B$ is the value of the min-cost matching between $R$
and $B$, i.e.,
\[ \mbox{EMD}(R,B)= \min_{\pi: R \to B}
\sum_{p \in R} \|p-\pi(p)\|,
\]
where $\pi$ is a one-to-one mapping, and $\|\cdot\|$ is (say) the $L_1$ norm.

What are the space vs. approximation tradeoffs achievable by streaming
algorithms for this problem?
In particular, is there an $O(1)$-approximation algorithm using
$(\log n+\log \Delta)^{O(1)}$ space?

It is known that that there is an $O(\log \Delta)$-approximation algorithm using
that much space {{cite|Indyk-04}}.
That algorithm proceeds essentially by embedding EMD into $L_1$ {{cite|Charikar-02|IndykT-03}}.
However, any such embedding must incur at least $\Omega( \sqrt{\log \Delta})$
distortion {{cite|NaorS-06}}.
So one would need to do something else to get $O(1)$-approximation.

← Older revision		Revision as of 21:26, 11 November 2014
Line 23:		Line 23:
	distortion {{cite\|NaorS-06}}.		distortion {{cite\|NaorS-06}}.
	So one would need to do something else to get $O(1)$-approximation.		So one would need to do something else to get $O(1)$-approximation.
		+
		+	==Update==
		+
		+	It was shown that the decision version of the problem (distinguish the cases, when the EMD distance is at most $1$ vs. at least $D$ for $D = O(1)$) does not allow sketches of the constant size {{cite\|AndoniKR-14}}.

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

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 7: Estimating Earth-Mover Distance}}
+{{Header
-{{Infobox
+|title=Estimating Earth-Mover Distance
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Piotr Indyk
+|who=Piotr Indyk
 }}
 Consider a stream of red points $R$ and blue points $B$ from a 2-dimensional

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)