Johan Wästlund: Central limit theorems in combinatorial optimization

Abstract

A number of well-known combinatorial optimization problems deal with graphs with costs associated to the edges. These problems include minimum spanning tree, the traveling salesman problem, shortest path, and various matching and cover problems. If the edge-costs are random, several models are known or conjectured to exhibit a Gaussian limit distribution of the total cost of the optimal solution, also known as a "central limit theorem". I will discuss a number of results and conjectures in this direction, in particular an intriguing observation that for a fairly broad class of models, all the cumulants of the total cost appear to be positive.