Glossary · approach
Hungarian Method
Combinatorial algorithm that solves the assignment problem (n×n cost matrix, one-to-one minimum-cost matching) in polynomial time O(n³); Kuhn (1955) and Munkres (1957).
Hungarian AlgorithmKuhn-Munkres Algorithm
The Hungarian Method (also Kuhn-Munkres Algorithm) is the combinatorial optimisation algorithm that solves the assignment problem — one-to-one matching of n workers/resources to n tasks under an n×n cost matrix, minimising total cost — in polynomial time O(n³). Harold Kuhn introduced the algorithm in his 1955 paper in *Naval Research Logistics Quarterly*; the name was given in honour of the bipartite-matching theorems developed in the early 1900s by the Hungarian mathematicians Dénes König and Jenő Egerváry. James Munkres in 1957 recast the algorithm as a fully formal polynomial-time O(n³) procedure, hence the modern alternative name Kuhn-Munkres Algorithm. Operating principle: subtract row/column minima (row + column reduction), find a maximum matching on the zero-cost cells via the König-Egerváry theorem, if not perfect apply a sequential covering procedure to update the matrix, repeat until a perfect matching is found. Guaranteed optimum, polynomial time, combinatorial. Modern faster alternatives: LAP — shortest augmenting path (Jonker and Volgenant 1987, in practice 5-20 times faster); auction algorithm (Bertsekas 1988, parallelisation-friendly). Kuhn (1955), Munkres (1957).
Örnek
Given a 5×5 cost matrix where each technician's travel time to each customer is different, the Hungarian Method finds the one-to-one matching that minimises total travel time in seconds; 15-30% better than the intuitive assignment.