An optimal space lower bound for approximating MAX-CUT
Michael Kapralov, Dmitry Krachun · 2019
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output half of this value as the estimate for the size of the MAX-CUT. On the other extreme, for any fixed є > 0, if one allows Õ(n) space, a (1+є)-approximate solution to the MAX-CUT value can be obtained by storing an Õ(n)-size sparsifier that essentially preserves MAX-CUT value.