期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2003
卷号：100
期号：20
页码：11211-11215
DOI：10.1073/pnas.1635191100
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：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 {delta}2. For the minimum matching and traveling salesman problems in dimension d [≥] 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.
