mathematics//optimization//combinatorial optimization//assignment problem//Hungarian algorithm
The Hungarian algorithm is an exact method for the assignment problem that runs in polynomial time, \(O(n^3)\) in its modern forms, and it is the standard solver behind warehouse dispatch, the association of radar echoes with tracks and any one-to-one matching given as a cost matrix. Kuhn published it in 1955 and named it after the two Hungarian mathematicians, Kőnig and Egerváry, whose results it builds on.
The Hungarian algorithm is an exact method for the assignment problem that runs in polynomial time, O(n3)O(n^3)O(n3) in its modern forms, and it is the standard solver behind warehouse dispatch, the association of radar echoes with tracks and any one-to-one matching given as a cost matrix. Kuhn published it in 1955 and named it after the two Hungarian mathematicians, Kőnig and Egerváry, whose results it builds on.
Its intuition fits in one observation. Every complete assignment uses exactly one entry of each row and one of each column, so subtracting a constant from a whole row (or a whole column) lowers the cost of every assignment by the same amount and leaves the best one unchanged. The algorithm subtracts row and column constants until a complete assignment can be made using only zeros; that assignment is optimal in the reduced matrix, hence in the original. On the matrix (122100)\left(\begin{smallmatrix}1&2\2&100\end{smallmatrix}\right)(122100), subtracting the row minima 1 and 2 and then the column minimum 1 leaves zeros at both off-diagonal positions; the crossed assignment costs 2+2=42+2=42+2=4, exactly the sum 1+2+11+2+11+2+1 of the constants removed.
The constants are a proof of optimality. Their sum is a lower bound on the cost of every assignment, since no entry ever goes negative, and an all-zero assignment meets that bound; the constants are the dual prices of the problem (duality), and auctions raise the same prices in a decentralized way.
In practice nobody writes it by hand. scipy.optimize.linear_sum_assignment implements a modern variant (Jonker-Volgenant), accepts rectangular matrices and solves a 1000 by 1000 case in under a second on a laptop, a few hundred agents in milliseconds. A fleet server runs it every few seconds with fresh travel times; a tracker runs it on every radar scan.
The cubic cost sets its range. Hundreds or a few thousand agents are routine; much larger sparse problems use variants that skip impossible pairs. The real limit is elsewhere: the algorithm needs the whole matrix in one place, which a swarm without a server does not have (the auction algorithm answers that case).
It solves linear sums only. As soon as the value of sending an agent depends on who else goes to the same task, the objective stops being a sum of matrix entries and the algorithm no longer applies (weapon-target assignment).