Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut

Lukas Michel, Alex Scott

Local search algorithms for NP-hard problems such as Max-Cut frequently perform much better in practice than worst-case analysis suggests. Smoothed analysis has proved an effective…