On the Smoothed Complexity of Combinatorial Local Search
Preprint
Abstract
We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a diverse selection of problems within the complexity class PLS can be cast within this model. This abstraction allows us to identify key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. We formalize this via a black-box tool that provides concrete bounds on the expected maximum number of steps needed until local search reaches an exact local optimum. This bound is particularly strong, in the sense that it holds for any starting feasible solution, any choice of pivoting rule, and does not rely on the choice of specific noise distributions that are applied on the input, but it is parameterized by just a global upper bound $\phi$ on the probability density. We then demonstrate the power of this tool, by instantiating it for various PLS-hard problems to derive efficient smoothed running times. This not only unifies, and greatly simplifies, prior existing positive results, but also allows us to extend or improve them. Notable problems on which we provide such a contribution are Max-Cut, the Travelling Salesman problem, and Network Coordination Games. Additionally, in this paper we propose novel smoothed analysis formulations, and prove polynomial smoothed running times, for important local optimization problems that have not been studied before from this perspective. Importantly, we provide an extensive study of the problem of finding pure Nash equilibria in general and Network Congestion Games under various representation models, including explicit, step-function, and polynomial latencies. We show that all the problems we study can be solved by their standard local search algorithms in polynomial smoothed time on PLS-hard instances in which these algorithms have exponential worst-case running time.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem2015
- 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
- On the Power of Nodes of Degree Four in the Local Max-Cut Problem2010
- Theoretical Aspects of Local Search2007
- The Traveling Salesman Problem and Its Variations2007
- Potential GamesGames and Economic Behavior, 1996
- On the hardness of global and local approximation1996
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973