On the Smoothed Complexity of Combinatorial Local Search
- 22 September 2025
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Abstract
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).Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem2015
- Bounds on the Maximum of the Density for Sums of Independent Random VariablesJournal of Mathematical Sciences, 2014
- Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSPAlgorithmica, 2013
- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise2013
- Settling the Complexity of Local Max-Cut (Almost) Completely2011
- On the Complexity of Local Search for Weighted Standard Set Problems2010
- Smoothed analysis of integer programmingMathematical Programming, 2007
- The Traveling Salesman Problem and Its Variations2007
- Potential GamesGames and Economic Behavior, 1996
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973