On the stability of solutions to random optimization problems under small perturbations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917819754479616 |
|---|---|
| author | Chatterjee, Sourav Ray, Souvik |
| author_facet | Chatterjee, Sourav Ray, Souvik |
| contents | Consider the Euclidean traveling salesman problem with $n$ random points on the plane. Suppose that one of the points is shifted to a new random location. This gives us a new optimal path. Consider such shifts for each of the $n$ points. Do we get $n$ very different optimal paths? In this article, we show that this is not the case - in fact, the number of truly different paths can be at most $\mathcal{O}(1)$ as $n\to \infty$. The proof is based on a general argument which allows us to prove similar stability results in a number of other settings, such as branching random walk, the Sherrington-Kirkpatrick model of mean-field spin glasses, the Edwards-Anderson model of short-range spin glasses, and the Wigner ensemble of random matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21513 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the stability of solutions to random optimization problems under small perturbations Chatterjee, Sourav Ray, Souvik Probability Discrete Mathematics Mathematical Physics Combinatorics 90C27, 60C05, 82B44, 82D30 Consider the Euclidean traveling salesman problem with $n$ random points on the plane. Suppose that one of the points is shifted to a new random location. This gives us a new optimal path. Consider such shifts for each of the $n$ points. Do we get $n$ very different optimal paths? In this article, we show that this is not the case - in fact, the number of truly different paths can be at most $\mathcal{O}(1)$ as $n\to \infty$. The proof is based on a general argument which allows us to prove similar stability results in a number of other settings, such as branching random walk, the Sherrington-Kirkpatrick model of mean-field spin glasses, the Edwards-Anderson model of short-range spin glasses, and the Wigner ensemble of random matrices. |
| title | On the stability of solutions to random optimization problems under small perturbations |
| topic | Probability Discrete Mathematics Mathematical Physics Combinatorics 90C27, 60C05, 82B44, 82D30 |
| url | https://arxiv.org/abs/2410.21513 |