Difference between revisions of "Open Problems:45"
(Created page with "{{Header |title=Streaming Max-Cut/Max-CSP |source=bertinoro11 |who=Robert Krauthgamer }} The problem is defined as follows: given a stream of edges of an $n$-node graph $G$, e...") |
(No difference)
|
Revision as of 04:10, 17 November 2012
| 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.
