Smoothed Analysis of Local Search for the Maximum-Cut Problem

Even though local search heuristics are the method of choice in practice for many well-studied optimization problems, most of them behave poorly in the worst case. This is, in particular, the case ...