On the Smoothed Complexity of Combinatorial Local Search
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908552991342592 |
|---|---|
| author | Giannakopoulos, Yiannis Grosz, Alexander Melissourgos, Themistoklis |
| author_facet | Giannakopoulos, Yiannis Grosz, Alexander Melissourgos, Themistoklis |
| contents | 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 $ϕ$ on the probability density. The power of this tool can be demonstrated by instantiating it for various PLS-hard problems of interest to derive efficient smoothed running times (as a function of $ϕ$ and the input size).
Most notably, we focus on the important local optimization problem of finding pure Nash equilibria in Congestion Games, that has not been studied before from a smoothed analysis perspective. Specifically, we propose novel smoothed analysis models for general and Network Congestion Games, under various representations, including explicit, step-function, and polynomial resource latencies. We study PLS-hard instances of these problems and show that their standard local search algorithms run in polynomial smoothed time.
Finally, we present further applications of our framework to a wide range of additional combinatorial problems, including local Max-Cut in weighted graphs, the Travelling Salesman problem (TSP) under the $k$-opt local heuristic, and finding pure equilibria in Network Coordination Games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07547 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Smoothed Complexity of Combinatorial Local Search Giannakopoulos, Yiannis Grosz, Alexander Melissourgos, Themistoklis Computational Complexity Computer Science and Game Theory 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 $ϕ$ on the probability density. The power of this tool can be demonstrated by instantiating it for various PLS-hard problems of interest to derive efficient smoothed running times (as a function of $ϕ$ and the input size). Most notably, we focus on the important local optimization problem of finding pure Nash equilibria in Congestion Games, that has not been studied before from a smoothed analysis perspective. Specifically, we propose novel smoothed analysis models for general and Network Congestion Games, under various representations, including explicit, step-function, and polynomial resource latencies. We study PLS-hard instances of these problems and show that their standard local search algorithms run in polynomial smoothed time. Finally, we present further applications of our framework to a wide range of additional combinatorial problems, including local Max-Cut in weighted graphs, the Travelling Salesman problem (TSP) under the $k$-opt local heuristic, and finding pure equilibria in Network Coordination Games. |
| title | On the Smoothed Complexity of Combinatorial Local Search |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2211.07547 |