Difference between revisions of "Open Problems:64"
m |
m (Krzysztof Onak moved page Waiting:Andrew McGregor to Open Problems:64) |
(No difference)
| |
Revision as of 22:58, 13 June 2014
| Suggested by | Andrew McGregor |
|---|---|
| Source | Bertinoro 2014 |
| Short link | https://sublinear.info/64 |
Consider an unweighted graph on $n$ nodes defined by a stream of edge insertions and deletions. Is it possible to approximate the size of the maximum cardinality matching up to constant factor given a single pass and $o(n^2)$ space? Recall that a factor 2 approximation is easy in $O(n \log n)$ space if there are no edge deletions.
