Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909326669512704 |
|---|---|
| author | Michel, Lukas Scott, Alex |
| author_facet | Michel, Lukas Scott, Alex |
| contents | Local search algorithms for NP-hard problems such as Max-Cut frequently perform much better in practice than worst-case analysis suggests. Smoothed analysis has proved an effective approach to understanding this: a substantial literature shows that when a small amount of random noise is added to input data, local search algorithms typically run in polynomial or quasi-polynomial time. In this paper, we provide the first example where a local search algorithm for the Max-Cut problem fails to be efficient in the framework of smoothed analysis. Specifically, we construct a graph with $n$ vertices where the smoothed runtime of the 3-FLIP algorithm can be as large as $2^{Ω(\sqrt{n})}$.
Additionally, for the setting without random noise, we give a new construction of graphs where the runtime of the FLIP algorithm is $2^{Ω(n)}$ for any pivot rule. These graphs are much smaller and have a simpler structure than previous constructions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_19594 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut Michel, Lukas Scott, Alex Data Structures and Algorithms Computational Complexity Local search algorithms for NP-hard problems such as Max-Cut frequently perform much better in practice than worst-case analysis suggests. Smoothed analysis has proved an effective approach to understanding this: a substantial literature shows that when a small amount of random noise is added to input data, local search algorithms typically run in polynomial or quasi-polynomial time. In this paper, we provide the first example where a local search algorithm for the Max-Cut problem fails to be efficient in the framework of smoothed analysis. Specifically, we construct a graph with $n$ vertices where the smoothed runtime of the 3-FLIP algorithm can be as large as $2^{Ω(\sqrt{n})}$. Additionally, for the setting without random noise, we give a new construction of graphs where the runtime of the FLIP algorithm is $2^{Ω(n)}$ for any pivot rule. These graphs are much smaller and have a simpler structure than previous constructions. |
| title | Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2310.19594 |