Skip to main content
eScholarship
Open Access Publications from the University of California

Scaling and universality in continuous length combinatorial optimization

  • Author(s): Aldous, D
  • Percus, AG
  • et al.
Abstract

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.

Main Content
Current View