On the Smoothed Complexity of Combinatorial Local Search

We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reaches an exact local optimum. We demonstrate its power by instantiating it for various PLS-hard problems of interest to derive efficient smoothed running times. Most notably, we introduce smoothed analysis models for finding pure Nash equilibria in congestion games and network congestion games under various representations of resource latency functions. We show that even for PLS-hard instances, better-response dynamics terminate in polynomial smoothed time. Further applications include local maximum-cut on weighted graphs, the travelling salesman problem under the k-Opt heuristic, and network coordination games.

Funding: A. Grosz was supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (Bundesministerium für Bildung und Forschung).