Scaling and Universality in Continuous Length Combinatorial Optimization

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 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.

5 pages; 3 figures

References in corpus (5)

• Nature of the Spin Glass State
• Spin and link overlaps in 3-dimensional spin glasses
• On the Effects of a Bulk Perturbation on the Ground State of 3D Ising Spin Glasses
• Zero Temperature Properties of RNA Secondary Structures
• A Proof of Parisi's Conjecture on the Random Assignment Problem

Cited by in corpus (19)

• A survey of max-type recursive distributional equations
• Extremal Properties of Random Structures
• Equilibrium statistical mechanics of network structures
• Information Dynamics in the Networked World
• A Tractable Complex Network Model based on the Stochastic Mean-field Model of Distance
• Networking - A Statistical Physics Perspective
• A frozen glass phase in the multi-index matching problem
• Near optimal configurations in mean field disordered systems
• Tracing the Evolution of Physics on the Backbone of Citation Networks
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• Analytical calculation of neighborhood order probabilities for high dimensional Poissonic processes and mean field models
• Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
• Minimum spanning trees and random resistor networks in d dimensions
• Replica Symmetry and Combinatorial Optimization
• Linear Phase Transition in Random Linear Constraint Satisfaction Problem
• Processes on Unimodular Random Networks
• Edge Flows in the Complete Random-Lengths Network
• Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models
• Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions