Open Problems:64 - Revision history

Krzysztof Onak: Fixing a citation

2017-04-28T05:01:18Z

Fixing a citation

2017-04-28T04:35:05Z

2017-04-20T16:12:00Z

2014-06-13T22:58:56Z

2014-06-13T22:58:25Z

2014-06-13T22:29:54Z

2014-06-13T22:29:30Z

2014-06-04T04:16:59Z

2014-05-28T21:41:43Z

2014-05-28T15:59:06Z

Created page with "{{Header |title=Matchings in the Turnstile Model |source=bertinoro14 |who=Andrew McGregor }} ???"

New page

{{Header
|title=Matchings in the Turnstile Model
|source=bertinoro14
|who=Andrew McGregor
}}
???

← Older revision		Revision as of 05:01, 28 April 2017
Line 6:		Line 6:

	== Updates ==		== 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\|~~AssadiKLY16~~\|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}}.	+	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}}.

@@ Line 5: / Line 5: @@
 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 ==
+== 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|AssadiKLY16|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}}.

← Older revision		Revision as of 16:12, 20 April 2017
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.

@@ Line 4: / Line 4: @@
 |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.

@@ Line 4: / Line 4: @@
 |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.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro14
 |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.

← Older revision	Revision as of 22:58, 13 June 2014
(No difference)

← Older revision		Revision as of 04:16, 4 June 2014
Line 5:		Line 5:
	}}		}}

−	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 ) ?	+	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)?