Scaling and universality in continuous length combinatorial optimization.
Where this comes from
- Record sourced from PubMed, PMID 14504403.
- Also identified by PMC identifier 208736.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
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.