Title: A Notion of Stability for Solutions of Random Optimization Problems.

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 talk, we show that this is not the case — in fact, the number of truly different paths can be at most O(1) as n goes to infinity. 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, the Wigner and Wishart ensemble of random matrices and combinatorial optimization problems on weighted complete graphs.

Share this Event