Local Max-Cut on Sparse Graphs

Gregory Schwartzman

We bound the smoothed running time of the FLIP algorithm for local Max-Cut as a function of $\alpha$, the arboricity of the input graph. We show that, with high probability and in expec…