Difference between revisions of "Open Problems:45"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Updates)
Line 19: Line 19:
 
== Updates ==
 
== Updates ==
 
The progress on the MAX-CUT problem in the streaming setting:
 
The progress on the MAX-CUT problem in the streaming setting:
* Estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space {{cite|KapralovKS-15|KoganK-15}}.
+
* Estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space {{cite|Kapralov-Khanna-Sudan'15|Kogan-Krauthgamer'15}}.
* There exists a constant $\varepsilon_*>0$ such that obtaining a $(1-\varepsilon_*)$ approximation to MAX-CUT requires $\Omega(n)$ space {{cite|KapralovKSV-17}}.
+
* There exists a constant $\varepsilon_*>0$ such that obtaining a $(1-\varepsilon_*)$ approximation to MAX-CUT requires $\Omega(n)$ space {{cite|Kapralov-Khanna-Sudan-Velingker'17}}.
* In random-order streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation {{cite|KapralovKS-15}}.
+
* In random-order streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation {{cite|Kapralov-Khanna-Sudan'15}}.

Revision as of 03:32, 27 June 2022

Suggested by Robert Krauthgamer
Source Bertinoro 2011
Short link https://sublinear.info/45

The problem is defined as follows: given a stream of edges of an $n$-node graph $G$, estimate the value of the maximum cut in $G$.

Question: Is there an algorithm with an approximation factor strictly better than $1/2$ that uses $o(n)$ space?

Background: Note that $1/2$ is achievable using random assignment argument. Moreover, using sparsification arguments [Trevisan-09,AhnG-09], one can obtain a better approximation ratio using $O(n \operatorname{polylog} n)$ space. Woodruff and Bhattacharyya (private communication) noted that subsampling $O(n/\epsilon^2)$ edges gives, with high probability, an $\epsilon$-additive approximation for all cuts, and thus $1+\epsilon$ multiplicative approximation for MAX-CUT.

Question: What about general constraint satisfaction problems with fixed clause-length and alphabet-size? In this case it is even not known how to obtain $O(n \operatorname{polylog} n)$ space bound.

Updates

The progress on the MAX-CUT problem in the streaming setting: