Scaling and universality in continuous length combinatorial optimization

We consider combinatorial optimization problems defined over rancom ensembles and study how solution cost increases when the optimal solution undergoes a small perturbation S. For the minimum spanning tree, the increase in cost scales as delta(2). For the minimum matching and traveling salesman problems in dimension d greater than or equal to 2, the increase scales as delta(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.