On the Smoothed Complexity of Combinatorial Local Search
提出了组合局部优化问题的平滑分析统一框架，证明即使对PLS难问题，局部搜索在多项式步数内达到精确局部最优，适用于拥堵博弈、最大割、旅行商等问题的效率分析。
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).