Problem 64: Matchings in the Turnstile Model
Revision as of 04:16, 4 June 2014 by Krzysztof Onak (talk | contribs)
| Suggested by | Andrew McGregor |
|---|---|
| Source | Bertinoro 2014 |
| Short link | https://sublinear.info/64 |
Suppose we are in a turnstile model for graph streaming: this means that the stream consists of a sequence of edge insertions and deletions (with no edge being deleted before it's inserted). In this setting, can we design an algorithm for computing a matching that takes space $o(n^2)$ and gets a constant-factor approximation (or better)?
