Rigorous analysis of local search heuristics

Local search heuristics are standard methods in the optimizer's toolbox. These algorithms take as an input a candidate solution to an optimization problem and iteratively compute better solutions. Heuristics typically provide close-to-optimal solutions in much less running time than exact or approximation algorithms. Despite their practical usefulness, local search heuristics often have poor performance in the worst case. For many problems we know of instances where commonly used heuristics take prohibitively long to return a solution, or where they may return solutions that are far from optimal. This considerable gap between theory and practice is not satisfactory, as we would like to have some theoretical justification for using local search heuristics in practice. This dissertation broadly aims to enhance our understanding of local search heuristics. We analyze several heuristics using rigorous mathematical tools. We focus on three computational problems: the Travelling Salesperson Problem (TSP), k-Means clustering, and Max Cut. We consider these heuristics from the perspective of worst-case and beyond-worst-case analysis.

For the TSP, we perform a smoothed analysis of the well-known 2-opt heuristic, improving and simplifying previous results for the Euclidean TSP. We then consider two polynomial-time variants of 2-opt, showing that one has poor approximation performance while the other performs similary to 2-opt. We moreover analyze the complexity of counting 2-optimal tours, and estimate the number of such tours in random instances.

For k-Means clustering, we rigorously analyze the Hartigan-Wong method. This heuristic performs well in practice, but little was previously known about it theoretically. We show that even in one-dimensional instances, where k-Means can be solved optimally in polynomial time, the Hartigan-Wong method can take exponential time to find locally optimal clusterings. We also show that the heuristic leads to a PLS-complete local search problem. To augment these results we also perform the first smoothed analysis of the Hartigan-Wong method.

Finally, we analyze the Flip heuristic for Max Cut, and show that also this simple heuristic yields a PLS-complete local search problem even in Euclidean instances.