Open Problems:60 - Revision history

128.119.247.136 at 16:22, 26 June 2013

2013-06-26T16:22:19Z

Krzysztof Onak: updated header

2013-03-07T02:00:19Z

updated header

Krzysztof Onak at 05:14, 12 December 2012

2012-12-12T05:14:53Z

Andoni: Created page with "{{Header |title=Single-Pass Unweighted Matchings |source=dortmund12 |who=Andrew McGregor }} Suppose you have $O(n \hbox{polylog} n)$ memory and a single pass over a stream of ..."

2012-12-12T02:19:25Z

Created page with "{{Header |title=Single-Pass Unweighted Matchings |source=dortmund12 |who=Andrew McGregor }} Suppose you have $O(n \hbox{polylog} n)$ memory and a single pass over a stream of ..."

New page

{{Header
|title=Single-Pass Unweighted Matchings
|source=dortmund12
|who=Andrew McGregor
}}
Suppose you have $O(n \hbox{polylog} n)$ memory and a single pass over a stream of $m$ edges (arbitrarily ordered) on $n$ nodes. How well can you approximate the size of the maximum cardinality matching? A trivial greedy algorithm finds a $1/2$-approximation but that's still the best known algorithm in the general setting. Kapralov {{cite|Kapralov-12}} showed that achieving better than a $1-1/e$ approximation is impossible. If the stream is randomly ordered, Konrad et al. {{cite|KonradMM-12}} presented a $1/2 + 0.005$-approximation. Other variants of the question are also open, e.g., achieving a $(1-\epsilon)$ approximation with multiple passes (see, e.g., Ahn and Guha {{cite|AhnG-11}}) or the best approximation possible for maximum weighted matching in a single pass (see, e.g., Epstein et al. {{cite|EpsteinLMS-11}}).

@@ Line 3: / Line 3: @@
 |who=Andrew McGregor
 }}
-Suppose you have $O(n \operatorname{polylog} n)$ memory and a single pass over a stream of $m$ edges (arbitrarily ordered) on $n$ nodes. How well can you approximate the size of the maximum cardinality matching? A trivial greedy algorithm finds a $1/2$-approximation but that's still the best known algorithm in the general setting. Kapralov {{cite|Kapralov-12}} showed that achieving better than a $1-1/e$ approximation is impossible. If the stream is randomly ordered, Konrad et  al. {{cite|KonradMM-12}} presented a $1/2 + 0.005$-approximation. Other variants of the question are also open, e.g., achieving a $(1-\epsilon)$ approximation with multiple passes (see, e.g., Ahn and Guha {{cite|AhnG-11}}) or the best approximation possible for maximum weighted matching in a single pass (see, e.g., Epstein et al. {{cite|EpsteinLMS-11}}).
+Suppose you have $O(n \operatorname{polylog} n)$ memory and a single pass over a stream of $m$ edges (arbitrarily ordered) on $n$ nodes. How well can you approximate the size of the maximum cardinality matching? A trivial greedy algorithm finds a $1/2$-approximation but that's still the best known algorithm in the general setting. Kapralov {{cite|Kapralov-12}} showed that achieving better than a $1-1/e$ approximation is impossible. If the stream is randomly ordered, Konrad et  al. {{cite|KonradMM-12}} presented a $1/2 + 0.005$-approximation. Other variants of the question are also open, e.g., achieving a $(1-\epsilon)$ approximation in the minimum number of passes (see, e.g., Ahn and Guha {{cite|AhnG-11}}) or the best approximation possible for maximum weighted matching in a single pass (see, e.g., Epstein et al. {{cite|EpsteinLMS-11}}).

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=Andrew McGregor
 }}
 Suppose you have $O(n \operatorname{polylog} n)$ memory and a single pass over a stream of $m$ edges (arbitrarily ordered) on $n$ nodes. How well can you approximate the size of the maximum cardinality matching? A trivial greedy algorithm finds a $1/2$-approximation but that's still the best known algorithm in the general setting. Kapralov {{cite|Kapralov-12}} showed that achieving better than a $1-1/e$ approximation is impossible. If the stream is randomly ordered, Konrad et  al. {{cite|KonradMM-12}} presented a $1/2 + 0.005$-approximation. Other variants of the question are also open, e.g., achieving a $(1-\epsilon)$ approximation with multiple passes (see, e.g., Ahn and Guha {{cite|AhnG-11}}) or the best approximation possible for maximum weighted matching in a single pass (see, e.g., Epstein et al. {{cite|EpsteinLMS-11}}).