INTERDISCIPLINARY STOCHASTIC PROCESSES COLLOQUIUM Thursday Nov. 7th 380 Soda 3:10-4:00pm Speaker: David Aldous (UC Berkeley, Department of Statistics) Title: Mean-field combinatorial optimization, fixed point equations, and local weak convergence. Abstract: For probabilistic study of TSP-like combinatorial optimization (CO) problems, one needs a model for {n \choose 2} interpoint distances. Three convenient models are: uniform-Euclidean, disordered lattice, and mean-field. One can seek to study aspects of the first-order n \to \infty asymptotics in terms of the CO problem on the relevant n = \infty limit random structure. For MST this works smoothly in all 3 models. For TSP one can hope for explicit results only in the mean-field model. Its study leads to a fixed point equation for probability distributions, implicit in Mezard-Parisi (1986). The explicit statement opens the door to more sophisticated questions. For instance, comparing near-optimal to optimal TSP solutions via relative lengths and proportions of distinct edges reveals (via heuristic analytics/numerics) the anomalous scaling exponent 3. Remarkably, this is close to what simulations show for 2-dimensional TSP.