On the Smoothed Complexity of Combinatorial Local Search, with an Emphasis on Congestion Games

In this talk I will present a unifying framework for smoothed analysis of combinatorial local optimization problems and discuss how a diverse selection of problems within the complexity class PLS can be cast within this model. Our framework includes a black-box tool for bounding the expected maximum number of steps needed until local search reaches an *exact* local optimum. We instantiate this tool to rederive (and in some cases improve) existing positive results from the literature for various local search problem.

More importantly, for computing (pure Nash) equilibria in congestion games, we provide the first polynomial *smoothed* running time bounds, for PLS-hard instances of the problem, under various meaningful input representations including explicitly given, polynomial, and step-function latency functions. Finally, for the more relaxed notion of (1+ε)-approximate equilibria (under which the problem is known to remain PLS-hard, for *any* constant ε) we provide a totally different analysis that guarantees a smoothed FPTAS for general instances, i.e. running time polynomial on 1/ε, φ, and the game's description, where φ is an upper bound on the density of the random noise imposed on the resource costs under smoothed analysis.

This talk includes joint work with Alexander Grosz (TU Munich) and Themistoklis Melissourgos (Essex), and is based on the following papers:

https://arxiv.org/abs/2211.07547
https://arxiv.org/abs/2306.10600