Scaling and Universality in Continuous Length Combinatorial Optimization

Details Scaling and Universality in Continuous Length Combinatorial Optimization Scaling and Universality in Continuous Length Combinatorial Optimization

2003-01-04

arxiv.org/abs/cond-mat/0301035v2

Physics

Condensed Matter

Disordered Systems and Neural Networks

5 pages; 3 figures

Scientific paper

10.1073/pnas.1635191100

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.

Affiliated with

Also associated with

No associations

Rating

Scaling and Universality in Continuous Length Combinatorial Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scaling and Universality in Continuous Length Combinatorial Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaling and Universality in Continuous Length Combinatorial Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-289730