Combinatorial optimization over random data and its scaling exponents
This short document
gives a description of the topic. The relevant technical papers so far are
Scaling and Universality in Continuous length Combinatorial Optimization
(with Allon Percus).
Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model.
Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models
(with Charles Bordenave and Marc Lelarge).
Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions
(with Charles Bordenave and Marc Lelarge).