✦ LIBER ✦
An algorithm to solve the m × n assignment problem in expected time O(mn log n)
✍ Scribed by Richard M. Karp
- Publisher
- John Wiley and Sons
- Year
- 1980
- Tongue
- English
- Weight
- 428 KB
- Volume
- 10
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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.