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

Scaling and universality in continuous length combinatorial optimization.

  • Author(s): Aldous, David
  • Percus, Allon G
  • et al.

We consider combinatorial optimization problems defined over random ensembles and study how solution cost increases when the optimal solution undergoes a small perturbation delta. For the minimum spanning tree, the increase in cost scales as delta2. For the minimum matching and traveling salesman problems in dimension d >/= 2, the increase scales as delta3; 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's open access policies. Let us know how this access is important for you.

Main Content
Current View