Difference between revisions of "Open Problems:64"
(Created page with "{{Header |title=Matchings in the Turnstile Model |source=bertinoro14 |who=Andrew McGregor }} ???") |
|||
| Line 4: | Line 4: | ||
|who=Andrew McGregor | |who=Andrew McGregor | ||
}} | }} | ||
| − | + | ||
| + | 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 approximation (or better ) ? | ||
Revision as of 21:41, 28 May 2014
| 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 approximation (or better ) ?
