Asymptotics in the random assignment problem

DOI10.1007/BF01192719zbMath0767.60006MaRDI QIDQ1203927

David J. Aldous

Publication date: 10 March 1993

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

zbMATH Keywords

optimal costrandom assignment problem

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Related Items (38)

Asymptotic properties of random multidimensional assignment problems ⋮ Convergence of directed random graphs to the Poisson-weighted infinite tree ⋮ Asymptotic behavior of the expected optimal value of the multidimensional assignment problem ⋮ Stable matchings in high dimensions via the Poisson-weighted infinite tree ⋮ On the maximum of random assignment process ⋮ Lévy-Khintchine random matrices and the Poisson weighted infinite skeleton tree ⋮ The mean field traveling salesman and related problems ⋮ An assignment problem at high temperature ⋮ Weak disorder asymptotics in the stochastic mean-field model of distance ⋮ Extrema of a multinomial assignment process ⋮ Around the circular law ⋮ Replica symmetry of the minimum matching ⋮ Minimum Cost Matching in a Random Graph with Random Costs ⋮ Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph ⋮ Diameter of the Stochastic Mean-Field Model of Distance ⋮ Spectrum of non-Hermitian heavy tailed random matrices ⋮ Belief propagation for optimal edge cover in the random complete graph ⋮ Anomalous scaling of the optimal cost in the one-dimensional random assignment problem ⋮ On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph ⋮ Explosion and linear transit times in infinite trees ⋮ The ?(2) limit in the random assignment problem ⋮ Random assignment problems ⋮ Endogeny for the logistic recursive distributional equation ⋮ Efficient algorithms for three‐dimensional axial and planar random assignment problems ⋮ A survey of max-type recursive distributional equations ⋮ Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph ⋮ Rigorous results for mean field models for spin glasses ⋮ Eigenvector statistics of Lévy matrices ⋮ Invariant probability measures and dynamics of exponential linear type maps ⋮ Constructive bounds and exact expectations for the random assignment problem ⋮ The random fractional matching problem ⋮ The planted matching problem: phase transitions and exact results ⋮ The Effect of Adding Randomly Weighted Edges ⋮ The minimum perfect matching in pseudo-dimension 0 < q < 1 ⋮ A general method for lower bounds on fluctuations of random variables ⋮ A conversation with David J. Aldous ⋮ Asymptotic results for random multidimensional assignment problems ⋮ Degree distribution of shortest path trees and bias of network sampling algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Matchings in random regular bipartite digraphs
• Asymptotics for Euclidean minimal spanning trees on random points
• On the Expected Value of a Random Assignment Problem
• The growth and composition of branching populations
• On linear programs with random costs
• Martingale Inequalities, Interpolation and NP-Complete Problems
• A random tree model associated with random graphs
• The stable doubly infinite pedigree process of supercritical branching populations
• A Lower Bound on the Expected Cost of an Optimal Assignment

This page was built for publication: Asymptotics in the random assignment problem