THE FOLD / CO-OP / THE PULL REQUEST / THE HUNGARIAN
THE HUNGARIAN
minimum-cost assignment by reducing to zeros
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Hungarian algorithm solves the assignment problem: given n workers and n jobs with a cost for each pairing, find the one-to-one assignment of workers to jobs with minimum total cost — in O(n³), versus checking all n! matchings.
It works by subtracting constants from rows and columns of the cost matrix (which never changes which assignment is optimal) until enough zeros appear to form a complete zero-cost matching, guided by dual variables. It is the combinatorial-optimisation workhorse behind scheduling, tracking, and resource allocation.
LIT verified live: over 200 random cost matrices (n=2…6), the Hungarian assignment’s total cost equals the brute-force minimum over all n! permutations (window.__hungarian). FIG no framing; exact optimisation.
It works by subtracting constants from rows and columns of the cost matrix (which never changes which assignment is optimal) until enough zeros appear to form a complete zero-cost matching, guided by dual variables. It is the combinatorial-optimisation workhorse behind scheduling, tracking, and resource allocation.
LIT verified live: over 200 random cost matrices (n=2…6), the Hungarian assignment’s total cost equals the brute-force minimum over all n! permutations (window.__hungarian). FIG no framing; exact optimisation.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-pull-request — matching contributions to reviewers at least total cost, cleanly one-to-one. The Hungarian algorithm is that optimal pairing. AVAN (AI) built the instrument: the row/column reduction, the augmenting-path matching, the brute cross-check.
Credit as content: Harold Kuhn (1955), who named it ‘Hungarian’ for the earlier work of König and Egerváry; refined by James Munkres. The weave: David names the pull-request; I reduce the cost matrix to zeros and match on them, confirming the total cost equals the exhaustive minimum.
Credit as content: Harold Kuhn (1955), who named it ‘Hungarian’ for the earlier work of König and Egerváry; refined by James Munkres. The weave: David names the pull-request; I reduce the cost matrix to zeros and match on them, confirming the total cost equals the exhaustive minimum.
3 ONE DIMENSION
Subtracting each row’s minimum, then each column’s, creates zeros without changing the optimal assignment — because every complete assignment uses one cell per row, so shifting a whole row shifts every assignment’s cost equally.
4 TWO DIMENSIONS · INTERACTIVE
A cost matrix. The Hungarian algorithm finds the minimum-cost assignment (highlighted cells, one per row and column); the total is checked against a brute-force minimum over all permutations.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the optimal assignment, one cell per row and column, sitting on the reduced zeros.
AVAN’s addition (the inverse-companion): subtracting a constant from a whole row or column does not change which assignment is optimal — every complete assignment uses exactly one cell per row, so a row shift moves all assignments’ costs by the same amount. The inverse of ‘the cheapest matching’ is ‘the matching that is cheapest after you have zeroed out the unavoidable per-row and per-column minimums.’ The algorithm exploits this invariance: reduce until the optimum reveals itself as a zero-cost matching. Magenta is the n! matchings never enumerated; green is the reduced zeros where the optimum hides. Reduction reveals the answer without search — linear-programming duality made combinatorial, the same max-min pairing as König and max-flow.
LIT Genuine Hungarian algorithm (Kuhn 1955, on Konig-Egervary; Munkres). Verified live: the row/column-reduction + augmenting-path assignment returns a total cost equal to the brute-force minimum over all n! permutations for 200 random cost matrices of size n=2..6 (window.__hungarian.matchesBrute).
FIG No framing: the reduction, the matching, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — subtracting a constant from a row or column shifts every complete assignment's cost equally (each uses one cell per row), so the optimum is invariant and reveals itself as a zero-cost matching; magenta is the n! matchings, green the reduced zeros. Ties to Hopcroft-Karp/Konig and Ford-Fulkerson.
FIG No framing: the reduction, the matching, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — subtracting a constant from a row or column shifts every complete assignment's cost equally (each uses one cell per row), so the optimum is invariant and reveals itself as a zero-cost matching; magenta is the n! matchings, green the reduced zeros. Ties to Hopcroft-Karp/Konig and Ford-Fulkerson.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PULL REQUEST · David Lee Wise (ROOT0), with AVAN