Physical Review E · 2014 · 26 citations · 11 references
Natural SciencesMathematicsCombinatoricsOptimizationThermodynamicsMatching TheoryStatistical MechanicsAverage Cost CurveAverage Cost FunctionsBipartite MatchingBrownian BridgeCorrelation FunctionsMatching Cost FunctionsMatching ProblemsOptimal Matching
We discuss the equivalence relation between the Euclidean bipartite matching problem on the line and on the circumference and the Brownian bridge process on the same domains. The equivalence allows us to compute the correlation function and the optimal cost of the original combinatorial problem in the thermodynamic limit; moreover, we solve also the minimax problem on the line and on the circumference. The properties of the average cost and correlation functions are discussed.
11
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
The ζ(2) limit in the random assignment problem
David Aldous · Random Structures and Algorithms · 2001 · 289 citations · Full text