Difference between revisions of "Open Problems:64"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Fixing a citation)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Matchings in the Turnstile Model
 
 
|source=bertinoro14
 
|source=bertinoro14
 
|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.
  
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 ) ?
+
== Updates ==
 +
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|AssadiKLY-16|ChitnisCEHMMV-16}}. When the goal is only to estimate the value of maximum matching (as opposed to finding the edges), $\Omega(n/\alpha^2)$ space is necessary and $\widetilde{O}(n^2/\alpha^4)$ space is sufficient {{cite|AssadiKL-17}}.

Latest revision as of 05:01, 28 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.

Updates[edit]

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 [AssadiKLY-16,ChitnisCEHMMV-16]. When the goal is only to estimate the value of maximum matching (as opposed to finding the edges), $\Omega(n/\alpha^2)$ space is necessary and $\widetilde{O}(n^2/\alpha^4)$ space is sufficient [AssadiKL-17].