Difference between revisions of "Open Problems:60"
(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 ...") |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=dortmund12 | |source=dortmund12 | ||
|who=Andrew McGregor | |who=Andrew McGregor | ||
}} | }} | ||
| − | Suppose you have $O(n \ | + | 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}}). |
Latest revision as of 16:22, 26 June 2013
| Suggested by | Andrew McGregor |
|---|---|
| Source | Dortmund 2012 |
| Short link | https://sublinear.info/60 |
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 [Kapralov-12] showed that achieving better than a $1-1/e$ approximation is impossible. If the stream is randomly ordered, Konrad et al. [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 [AhnG-11]) or the best approximation possible for maximum weighted matching in a single pass (see, e.g., Epstein et al. [EpsteinLMS-11]).
