On the Smoothed Complexity of Combinatorial Local Search

• 成果类型: Article; Early Access
• 署名作者: Giannakopoulos, Yiannis; Melissourgos, Themistoklis; Grosz, Alexander
• 署名单位: University of Glasgow; Technical University of Munich; University of Essex
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0610
• 发表日期: 2025
• 关键词: 2-opt algorithm

摘要

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.