Difference between revisions of "Open Problems:64"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m
Line 4: Line 4:
 
|who=Andrew McGregor
 
|who=Andrew McGregor
 
}}
 
}}
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.

Revision as of 22:29, 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.