Scaling and universality in continuous length combinatorial optimization
- Author(s): Aldous, D
- Percus, AG
- et al.
Published Web Locationhttps://doi.org/10.1073/pnas.1635191100
We consider combinatorial optimization problems defined over random ensembles and study how solution cost increases when the optimal solution undergoes a small perturbation δ. For the minimum spanning tree, the increase in cost scales as δ2. For the minimum matching and traveling salesman problems in dimension d ≥ 2, the increase scales as δ3; this is observed in Monte Carlo simulations in d = 2, 3, 4 and in theoretical analysis of a mean-field model. We speculate that the scaling exponent could serve to classify combinatorial optimization problems of this general kind into a small number of distinct categories, similar to universality classes in statistical physics.
Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.