Premium
An algorithm to solve the m × n assignment problem in expected time O ( mn log n )
Author(s) -
Karp Richard M.
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100205
Subject(s) - independent and identically distributed random variables , algorithm , enhanced data rates for gsm evolution , queue , computer science , combinatorics , efficient algorithm , random variable , mathematics , mathematical optimization , discrete mathematics , statistics , artificial intelligence , programming language
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.