On the stability of solutions to random optimization problems under small perturbations
Abstract/Contents
- Abstract
- 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 work, we show that this is not the case --- in fact, the number of truly different paths is bounded as n becomes large. 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Ray, Souvik |
|---|---|
| Degree supervisor | Chatterjee, Sourav |
| Thesis advisor | Chatterjee, Sourav |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Diaconis, Persi |
| Degree committee member | Dembo, Amir |
| Degree committee member | Diaconis, Persi |
| Associated with | Stanford University, School of Humanities and Sciences |
| Associated with | Stanford University, Department of Statistics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Souvik Ray. |
|---|---|
| Note | Submitted to the Department of Statistics. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/nc904bn0891 |
Access conditions
- Copyright
- © 2023 by Souvik Ray
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...