Hungarian algorithm - Wikipedia

Abstraction: Polynomial-time combinatorial algorithm for optimal assignment problems

Key points:

• Solves the assignment problem (minimum-cost perfect matching in bipartite graphs) in O(n^3) time; published by Harold Kuhn in 1955 based on work by Kőnig and Egerváry
• Edmonds, Karp, and independently Tomizawa improved it to O(n^3); equivalent to the successive shortest path algorithm for min-cost flow
• Matrix formulation: subtract row/column minima, cover zeros with minimum lines, then adjust uncovered values iteratively
• Also called Kuhn-Munkres algorithm; James Munkres proved it is strongly polynomial in 1957
• Scipy implementation available as scipy.optimize.linear_sum_assignment
• Extension to sparse graphs runs in O(n(m + n log n)) using Fibonacci heaps

Connections: Hungarian Algorithm · Assignment Problem · Combinatorial Optimization · Bipartite Matching

Source: http://en.wikipedia.org/wiki/Hungarian_algorithm