https://sublinear.info/api.php?action=feedcontributions&feedformat=atom&user=128.119.247.136 2026-04-22T18:38:01Z User contributions MediaWiki 1.31.10 https://sublinear.info/index.php?title=Open_Problems:60&diff=693 2013-06-26T16:22:19Z

<p>128.119.247.136: </p> <hr /> <div>{{Header<br /> |source=dortmund12<br /> |who=Andrew McGregor<br /> }}<br /> 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}}).</div>

128.119.247.136