An algorithm to solve the m × n assignment problem in expected time O(mn log n)

We give an algorithm to solve the m‐source, n‐destination assignment problem in expected time O(mn log n) under the assumption that the edge costs are independent random variables and the costs of the edges incident with any given source are identically distributed. The algorithm achieves its efficiency through an unusual application of priority queues.