Comparing Mean Field and Euclidean Matching Problems

Abstract

Combinatorial optimization is a fertile testing ground for statistical physics methods developed in the context of disordered systems, allowing one to confront theoretical mean field predictions with actual properties of finite dimensional systems. Our focus here is on minimum matching problems, because they are computationally tractable while both frustrated and disordered. We first study a mean field model taking the link lengths between points to be independent random variables. For this model we find perfect agreement with the results of a replica calculation. Then we study the case where the points to be matched are placed at random in a d-dimensional Euclidean space. Using the mean field model as an approximation to the Euclidean case, we show numerically that the mean field predictions are very accurate even at low dimension, and that the error due to the approximation is O(1/d^2). Furthermore, it is possible to improve upon this approximation by including the effects of Euclidean correlations among k link lengths. Using k=3 (3-link correlations such as the triangle inequality), the resulting errors in the energy density are already less than 0.5% at d>=2. However, we argue that the Euclidean model's 1/d series expansion is beyond all orders in k of the expansion in k-link correlations.

11 pages, 1 figure

Cited by in corpus (19)

• Asymptotically Optimal Algorithms for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Scaling hypothesis for the Euclidean bipartite matching problem
• Random multi-index matching problems
• The stochastic traveling salesman problem: Finite size scaling and the cavity prediction
• Near optimal configurations in mean field disordered systems
• Quadratic stochastic Euclidean bipartite matching problem
• Exact solution of the random bipartite matching model
• Mean-Field Approximations to the Longest Common Subsequence Problem
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• Analytical calculation of neighborhood order probabilities for high dimensional Poissonic processes and mean field models
• One-loop diagrams in the Random Euclidean Matching Problem
• Finite-size corrections in the random assignment problem
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Distance statistics in random media: high dimension and/or high neighborhood order cases
• Phase transition in the bipartite z-matching
• Average optimal cost for the Euclidean TSP in one dimension
• The statistical mechanics of multi-index matching problems with site disorder
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs