Scaling and Universality in Continuous Length Combinatorial Optimization
<|reference_start|>Scaling and Universality in Continuous Length Combinatorial Optimization: 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 mean-field and Euclidean 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 into a small number of distinct categories, similar to universality classes in statistical physics.<|reference_end|>
@article{aldous2003scaling,
    title={Scaling and Universality in Continuous Length Combinatorial Optimization},
    author={David Aldous and Allon G. Percus},
    journal={arXiv preprint arXiv:cond-mat/0301035},
    year={2003},
    doi={10.1073/pnas.1635191100},
    number={LA-UR-02-7322},
    archivePrefix={arXiv},
    eprint={cond-mat/0301035},
    primaryClass={cond-mat.dis-nn cond-mat.stat-mech cs.DM}
}