Sketching Cuts in Graphs and Hypergraphs
Sketching Cuts in Graphs and Hypergraphs
Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that (1--ε)-approximation for Max-Cut must use n{1-O(ε)} space; moreover, beating 4/5-approximation requires polynomial space. For the sketching model, we show that every r-uniform hypergraph admits a (1+ …