THE HUNGARIAN ALGORITHM named for two Hungarians, found by a third man first
Assign n workers to n jobs, each pair with a cost, so the total is smallest — and do it in polynomial time, not by trying all n! matchings. The cost matrix is a 2-D array (the box’s open want). And the name hides a triple credit story: Kuhn named it to honour two Hungarians, and Jacobi had it a century earlier.
THE TECHNIQUE subtract, cover, augment
Reduce each row and column by its minimum (an assignment’s optimality doesn’t change if you subtract a constant from a whole row or column). Cover all zeros with the fewest lines; if n lines are needed, a zero-cost perfect assignment exists. Below: a cost matrix and its minimum-cost assignment, one cell per row and column. live demo
HISTORY & CREDIT a name that credits the wrong century
“Hungarian” — and its first author was neither Hungarian nor 20th-century; a German mathematician had it in the 1840s. cited
1840s · Carl Gustav Jacobi works out essentially the algorithm (as a subroutine of a differential-equations bound); first published posthumously in Latin (Crelle’s Journal, 1865; reprinted in his collected works, 1890), it lies unread until rediscovered around 2006 — Kuhn later wrote “How Jacobi Beat Me by 100 Years.” 1931 · the Hungarians Dénes Kőnig and Jenő Egerváry prove the matching/covering theorems the method rests on. 1953–55 · Harold Kuhn translates Egerváry’s Hungarian paper himself, assembles the algorithm, and — crediting his sources in the title — names it “the Hungarian method.” 1957 / 1970s · James Munkres gives the first rigorous polynomial-time proof (hence “Kuhn-Munkres”); the crisp O(n³) form is Tomizawa (1971) and Edmonds-Karp (1972).
A rare case where the discoverer under-claimed — and the true first author was silent in Latin for 116 years. Jacobi / Kőnig-Egerváry / Kuhn-Munkres
RECOMMEND FOR I-13 the cost matrix is a 2-D array
The whole method operates on an n×n cost matrix — row/column reductions, zero-covering, augmenting paths — which is a genuine 2-D array:
# cost matrix [[9,11,14],[6,15,13],[12,13,6]]
min assignment: w0->j1 (11), w1->j0 (6), w2->j2 (6) total = 23
Recommend: presses PS-004 (a 2-D array) — the same want Smith-Waterman (054) and knapsack (053) named. I-13’s array is 1-D, so an n×n matrix is either a flattened row-major 1-D array (index i*n+j — runs today, just with manual index math) or the genuine 2-D array the box lists. The reductions and coverings are indexed reads and writes; no bignum, no bitwise. Honest note: the flattened form runs now; a real 2-D array would let the row/column operations read like the textbook rather than as i*n+j arithmetic.