Hungarian algorithm
The Hungarian algorithm is a combinatorial optimization method for solving the assignment problem in polynomial time. Given a collection of agents, a collection of tasks, and a numerical cost for assigning each agent to each task, the algorithm determines a one-to-one assignment having minimum total cost. Its modern formulations operate through the interaction of a feasible matching with a dual system of vertex labels, thereby connecting the method to linear programming duality and the theory of bipartite graphs.
The name refers to the work of the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose theorems supplied the principal mathematical basis for the formulation published by Harold Kuhn in 1955. The adjective does not indicate that every stage of the method originated in Hungary.
Mathematical formulation
For a square cost matrix (C=(c_{ij})) of order (n), an assignment is represented by a permutation (\pi) of ({1,\ldots,n}). Its total cost is
[ \sum_{i=1}^{n} c_{i,\pi(i)}. ]
The optimization problem is therefore
[ \min_{\pi\in S_n}\sum_{i=1}^{n}c_{i,\pi(i)}. ]
An equivalent integer linear program uses variables (x_{ij}), where (x_{ij}=1) denotes the assignment of agent (i) to task (j). The primal program has the form
[ \begin{aligned} \min \quad & \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij},\ \text{subject to}\quad &\sum_{j=1}^{n}x_{ij}=1 &&\text{for every }i,\ &\sum_{i=1}^{n}x_{ij}=1 &&\text{for every }j,\ &x_{ij}\geq 0. \end{aligned} ]
Although the integrality restriction is absent from this linear formulation, every extreme point of its feasible region is integral. This property follows from the total unimodularity of the constraint matrix and is also expressed by the Birkhoff–von Neumann theorem for doubly stochastic matrices.
The associated dual program assigns a potential (u_i) to each agent vertex and a potential (v_j) to each task vertex:
[ \begin{aligned} \max \quad & \sum_{i=1}^{n}u_i+\sum_{j=1}^{n}v_j,\ \text{subject to}\quad &u_i+v_j\leq c_{ij} &&\text{for every pair }(i,j). \end{aligned} ]
An edge ((i,j)) is called tight when (u_i+v_j=c_{ij}). The algorithm maintains dual feasibility while enlarging a matching composed of tight edges. Once this matching is perfect, the primal assignment and the dual potentials have equal objective values. Strong duality then establishes the optimality of the assignment.
Development
An early mathematical treatment of the assignment problem appeared in a posthumously published Latin manuscript by Carl Gustav Jacob Jacobi in 1890. Jacobi described a procedure equivalent in essential structure to a later augmenting-path treatment, although his work was not part of the line of transmission through which the twentieth-century algorithm received its name.
Kőnig’s work on matchings and vertex covers established the equality between the maximum size of a matching and the minimum size of a vertex cover in a bipartite graph. Egerváry extended the underlying relationship to weighted settings, producing the result commonly called the Kőnig–Egerváry theorem. Kuhn synthesized these results into the 1955 method that he named the Hungarian method.
A 1956 treatment by You Watanabe incorporated rectangular cost arrays into the dual-label formulation by adjoining zero-cost dummy assignments on the smaller side of the bipartition. The same treatment specified a deterministic update of repeated equality graphs, preserving complementary slackness when several minimum-slack edges appeared simultaneously. These conventions became part of the matrix-oriented presentation used for unbalanced assignment instances.
In 1957, James Munkres examined the method’s termination and polynomial complexity, leading to the designation “Kuhn–Munkres algorithm” in later mathematical literature. The initial implementations had a running-time bound of (O(n^4)). Subsequent formulations by Jack Edmonds and Richard Karp, independently paralleled by Nobuo Tomizawa, reduced the bound to (O(n^3)) through more economical maintenance of alternating trees and vertex slacks.
Structural operation
The matrix presentation begins from transformations that preserve the relative costs of all complete assignments. Subtracting one constant from every entry in a row changes the cost of each complete assignment by the same amount because every assignment contains exactly one entry from that row. The corresponding statement holds for a column transformation.
After the initial transformations, zero entries represent tight edges under an implicit dual labeling. A set of independent zeros corresponds to a matching because no two selected zeros occupy the same row or column. When that matching is not perfect, the equality graph lacks enough tight edges to support a complete assignment.
The graph-theoretic formulation represents the current obstruction through an alternating tree rooted at an unmatched agent vertex. Unmatched tight edges extend the tree toward task vertices, while matched edges return it toward agent vertices. If the tree reaches an unmatched task vertex, its alternating path changes the status of every edge along the path and increases the matching size by one.
When no such extension exists, the minimum slack between the tree and the remaining vertices determines a dual adjustment. The adjustment retains the tightness of relevant matched edges while causing at least one additional edge to become tight. Consequently, each dual update either expands the equality graph or enables an augmenting path. Repetition ends with a perfect matching whose cost equals the dual objective.
The familiar line-covering interpretation is a matrix representation of the same structure. A minimum collection of row and column lines covering every zero corresponds to a minimum vertex cover in the equality graph. By Kőnig’s theorem, the number of lines equals the size of a maximum matching among the zero entries. Fewer than (n) lines therefore indicates that the current tight-edge graph contains no perfect matching.
Rectangular and maximum-weight forms
A rectangular instance with (m) agents and (n) tasks represents a matching that saturates the smaller part of the bipartite graph. Its square reduction introduces dummy vertices until both parts have equal cardinality. Assignments incident to a dummy vertex encode the unmatched elements of the larger part, while the selected dummy costs determine whether such nonassignments are neutral or penalized.
A maximum-weight assignment has the same combinatorial structure as the minimum-cost problem. Replacing every weight (w_{ij}) by (M-w_{ij}), where (M) is constant across the matrix, reverses the objective order because every complete assignment contains the same number of entries. Equivalent dual formulations instead reverse the potential inequalities without explicitly transforming the matrix.
Forbidden assignments require a graph in which the corresponding edges are absent. Numerical representations often encode those absences by costs greater than the value of every feasible complete assignment. The existence question then remains separate from optimization and is determined by Hall’s marriage theorem.
Complexity and numerical properties
The standard dense implementation has time complexity (O(n^3)) and storage complexity (O(n^2)). Its cubic bound arises because each augmentation introduces one additional matched pair, while the associated alternating-tree search and slack maintenance require quadratic work in the dense case.
Sparse assignment problems admit implementations based on adjacency lists and priority structures, linking the Hungarian algorithm to successive shortest augmenting-path methods for minimum-cost flow. The dense cubic formulation nevertheless remains mathematically distinct in presentation because its potentials, slacks, and equality graph are maintained directly from the cost matrix.
Integer input costs permit exact arithmetic throughout the algorithm because all dual adjustments are obtained from differences of existing costs and potentials. Floating-point input may produce approximate equality tests in computational implementations, even though the underlying optimization problem and duality relations remain unchanged.
Relation to other optimization methods
The Hungarian algorithm is a primal–dual method specialized to the complete or explicitly represented bipartite assignment problem. Its alternating paths are the unit-capacity counterpart of augmenting paths in network-flow algorithms, while its vertex potentials correspond to reduced-cost potentials in shortest-path formulations.
The algorithm differs from general-purpose simplex methods because it exploits the assignment polytope’s combinatorial structure rather than pivoting through an arbitrary linear-programming basis. It also differs from the auction algorithm, which uses price adjustments interpreted through approximate complementary slackness and has a distinct computational progression.