Scaling and universality in continuous length combinatorial optimization

AUTOR(ES)

Aldous, David

FONTE

National Academy of Sciences

RESUMO

We consider combinatorial optimization problems defined over random ensembles and study how solution cost increases when the optimal solution undergoes a small perturbation δ. For the minimum spanning tree, the increase in cost scales as δ2. For the minimum matching and traveling salesman problems in dimension d ≥ 2, the increase scales as δ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.

Documentos Relacionados

• Optimization and control of a continuous polymerization reactor
• Gait dynamics in Parkinson’s disease: Common and distinct behavior among stride length, gait variability, and fractal-like scaling
• Continuous Culture Used for Media Optimization
• Relações min-max em otimização combinatória
• SIMULTANEOUS SCHEDULING AND OPERATIONAL OPTIMIZATION OF MULTIPRODUCT, CYCLIC CONTINUOUS PLANTS