The Hungarian algorithm for assignment problems
Suppose a company must assign workers to tasks, drivers to routes, or machines to jobs. Each possible pairing has a cost, such as time, distance, or money, and every worker should receive exactly one task. The assignment problem asks for the complete pairing with the smallest total cost.
Trying every possible matching quickly becomes impractical. With (n) workers and (n) tasks, there are (n!) possible assignments. Even moderate values of (n) produce an enormous search space. The Hungarian algorithm solves this optimization problem in polynomial time while preserving the structure of the cost matrix.
The method is especially useful because it combines a clear mathematical idea with an implementation that relies on elementary matrix operations and graph concepts. Learning it also builds intuition for duality, augmenting paths, and how local zero-cost choices can reveal a global optimum.
Modeling the assignment problem
Represent the problem with a cost matrix (C). Row (i) represents a worker, machine, or agent, while column (j) represents a task. The value (C_{ij}) is the cost of assigning row (i) to column (j). A valid solution selects exactly one cell from every row and every column.
If (x_{ij}) is 1 when row (i) is assigned to column (j), and 0 otherwise, the objective is
[ \min \sum_{i=1}^{n}\sum_{j=1}^{n} C_{ij}x_{ij} ]
subject to
[ \sum_j x_{ij}=1 \quad\text{and}\quad \sum_i x_{ij}=1. ]
These constraints enforce a perfect matching. The same formulation works for maximization by transforming rewards into costs. A common transformation is (C'{ij}=M-C{ij}), where (M) is at least the largest reward. Minimizing the transformed values then maximizes the original rewards.
The basic version assumes a square matrix. If there are more workers than tasks, or more tasks than workers, add dummy rows or columns. Their entries usually receive zero cost when leaving an unmatched agent or task is allowed. For forbidden pairings, use a sufficiently large penalty rather than an ordinary zero.
Why subtracting values preserves the answer
The Hungarian algorithm begins by subtracting the smallest value in each row from every entry in that row. This creates at least one zero in every row. It then performs the same operation on each column, ensuring that every column also contains a zero.
These transformations change the numerical values but do not change which assignment is optimal. Every complete assignment uses exactly one value from each row, so subtracting a row constant decreases the cost of every complete assignment by the same amount. Column subtraction has the same property. Since all candidate assignments shift equally, their relative ordering remains unchanged.
The zeros are useful because they mark pairings with no remaining reduced cost. If one zero can be selected from every row and every column, that selection is optimal. The challenge is that zeros may conflict: several rows can have their only zero in the same column. The algorithm therefore needs a systematic way to create and organize additional zeros.
This principle resembles reduced costs in linear programming. For a broader view of how constraints and objective functions can be transformed while retaining an optimum, the simplex algorithm provides useful complementary context.
Finding independent zeros
After row and column reduction, the algorithm tries to select independent zeros. “Independent” means that no two selected zeros share a row or column. A selected zero is often called starred, while a zero temporarily used during the search can be called primed.
If there are (n) independent starred zeros in an (n \times n) matrix, the assignment is complete. Otherwise, cover every column containing a starred zero with a line. In some presentations, rows and columns are covered during a marking procedure, but the goal is the same: determine whether the current zero structure is sufficient.
When fewer than (n) lines are needed to cover all zeros, the matrix does not yet contain a complete independent set. Find the smallest uncovered value, subtract it from every uncovered entry, and add it to entries covered twice. Leave entries covered exactly once unchanged. This operation creates at least one new zero without destroying the cost-preserving structure.
The line-cover step is connected to matching theory. A maximum matching in a bipartite graph corresponds to the largest set of independent zeros, while a minimum vertex cover identifies the smallest set of rows and columns covering all zero edges. This relationship explains why the algorithm can use the number of covering lines as a certificate of progress.
Augmenting paths and alternating choices
When a new uncovered zero appears, mark it as primed. If its row has no starred zero, trace an alternating path that begins with this primed zero. The path alternates between primed and starred zeros: move from a primed zero to the starred zero in its column, then across that row to another primed zero, continuing until reaching a primed zero whose column has no starred zero.
Switch the status along this path. Primed zeros become starred, and previously starred zeros become unstarred. The number of selected assignments increases by one, while no row or column receives two starred zeros. Then erase the temporary primes and reset the covers before searching again.
If the row containing a new zero already has a starred zero, the zero cannot immediately extend the assignment. Prime it, cover that row, and uncover the column containing its starred zero. Continue searching for another uncovered zero. If none exists, adjust the matrix with the smallest uncovered value and repeat.
This alternating-path process is the same core idea used in bipartite matching algorithms. Rather than committing permanently to the first available zero, it can rearrange earlier choices. That ability to revise a partial matching is what prevents greedy decisions from blocking the optimum.
A practical implementation workflow
A straightforward implementation can store the matrix in a two-dimensional array and maintain three additional structures: a Boolean array for covered rows, a Boolean array for covered columns, and arrays identifying starred and primed zeros. The exact data structures may vary, but separating permanent assignments from temporary search marks makes the code easier to debug.
A high-level workflow looks like this:
- Convert the input into a square minimization matrix.
- Subtract the minimum value from every row.
- Subtract the minimum value from every column.
- Star zeros greedily when their row and column are unused.
- Cover columns containing starred zeros.
- If every column is covered, read the starred positions as the solution.
- Otherwise, find an uncovered zero and prime it.
- Build an alternating path or adjust the matrix when no suitable zero remains.
- Repeat until every row has a starred assignment.
The classic algorithm runs in (O(n^3)) time and uses (O(n^2)) space when the matrix itself dominates storage. This is substantially better than enumerating (n!) assignments. For a useful comparison with other algorithmic growth rates, the discussion of sorting time complexity helps place cubic time in context.
In production code, keep the original cost matrix if the final cost must be reported. The reduced matrix is an internal working representation, so its entries do not directly equal the original assignment costs. After extracting the row-column pairs, calculate the total from the untouched input.
Comparing common solution strategies
Different approaches may produce an assignment, but they differ greatly in guarantees and scalability. The Hungarian algorithm is generally the best-known direct method for dense assignment matrices, while other techniques can be preferable when the graph is sparse or the problem has additional constraints.
| Method | Typical time complexity | Optimal assignment guaranteed? | Useful when |
|---|---|---|---|
| Brute-force enumeration | (O(n!)) | Yes | Very small inputs or testing |
| Greedy smallest-cost pairing | Usually (O(n^2 \log n)) | No | A quick heuristic is acceptable |
| Min-cost max-flow | Varies, often higher on dense graphs | Yes | Extra flow constraints are present |
| Hungarian algorithm | (O(n^3)) | Yes | Standard dense one-to-one assignment |
| Dynamic programming over subsets | (O(n2^n)) | Yes | Small (n), with bitmask-friendly logic |
Greedy selection can fail even when it picks the cheapest available edge at every step. A cheap edge may consume the only useful column for another row, forcing an expensive final assignment. The Hungarian algorithm avoids this trap by considering the entire zero structure and using alternating paths to revise earlier matches.
Min-cost max-flow is more flexible when capacities, multiple units, or network structure matter. The assignment problem can be represented as a flow network, but that generality may add implementation overhead. Conversely, the Hungarian method is specialized: its assumptions are a source of efficiency, but unusual constraints may require a more general model.
Edge cases, verification, and debugging
Negative costs are valid if the implementation handles them consistently. Row and column reductions still work because subtracting a minimum remains well-defined. For maximization, avoid careless integer overflow when converting rewards into costs, especially if using a large sentinel value for forbidden assignments.
Rectangular input deserves explicit treatment. Padding with dummy entries changes the interpretation of the result, so the program should distinguish real assignments from matches involving dummy rows or columns. If forbidden pairs are represented by a huge number, verify that the final matching never uses one unless no feasible assignment exists.
A useful test strategy includes matrices with tied values, a single row, already reduced matrices, negative entries, and cases where the greedy matching fails. Compare the algorithm’s result with brute force on small random matrices. This catches errors in cover resetting, alternating-path construction, and the smallest-uncovered-value adjustment.
For large numerical values, use an integer type wide enough for both intermediate reductions and the final sum. For floating-point costs, introduce a tolerance when deciding whether an entry is zero. Exact equality checks can fail after arithmetic operations, causing the search for zeros to behave unpredictably.
Recommendations for applying the method
- Keep the original matrix separate from the reduced working matrix.
- Normalize maximization and minimization into one consistent internal form.
- Use brute-force verification on small random cases during development.
- Represent assignments explicitly as row-column pairs rather than relying on matrix positions alone.
- Document how dummy entries and forbidden pairings are interpreted.
The Hungarian algorithm is a strong example of how algebraic transformations and graph matching reinforce each other. Matrix reductions expose useful zero-cost edges, while alternating paths turn those edges into a globally optimal assignment. Its (O(n^3)) complexity makes the approach practical for many dense scheduling and matching tasks.
Implement it first with clear helper functions for reduction, zero marking, cover management, and path augmentation. Then test each phase independently before optimizing storage or constant factors. If an implementation behaves unexpectedly, share the details through the hello ML contact page and continue exploring related algorithm and machine learning explanations on the site.