Difference between revisions of "Open Problems:64"
| Line 4: | Line 4: | ||
}} | }} | ||
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. | 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. | ||
| + | |||
| + | == Update == | ||
| + | |||
| + | The question is fully settled when the goal is to output the edges of an approximate maximum matching: to obtain an $\alpha$-approximation to maximum matching in dynamic streams, $\Omega(n^2/\alpha^3)$ space is necessary {{cite|AssadiKLY-16}} and $\widetilde{O}(n^2/\alpha^3)$ space is sufficient {{cite|AssadiKLY16|ChitnisCEHMMV-16}}. When the goal is only to estimate the value of maximum matching (as opposed to finding the edges), it was shown in {{cite|AssadiKL-17}} that $\Omega(n/\alpha^2)$ space is necessary and $\widetilde{O}(n^2/\alpha^4)$ space is sufficient. | ||
Revision as of 16:12, 20 April 2017
| 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.
Update
The question is fully settled when the goal is to output the edges of an approximate maximum matching: to obtain an $\alpha$-approximation to maximum matching in dynamic streams, $\Omega(n^2/\alpha^3)$ space is necessary [AssadiKLY-16] and $\widetilde{O}(n^2/\alpha^3)$ space is sufficient [AssadiKLY16,ChitnisCEHMMV-16]. When the goal is only to estimate the value of maximum matching (as opposed to finding the edges), it was shown in [AssadiKL-17] that $\Omega(n/\alpha^2)$ space is necessary and $\widetilde{O}(n^2/\alpha^4)$ space is sufficient.
