The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in cubic time, or $O(n^3)$ complexity, by reducing a square cost matrix to find the exact minimum-cost one-to-one pairing between $n$ workers and $n$ tasks. Also known as the Kuhn–Munkres algorithm, it operates by manipulating row and column potentials to identify a complete bipartite matching of minimum total weight. It requires a complete, square, finite-cost matrix where every cell represents the numerical cost of assigning a specific worker to a specific task. By systematically subtracting the minimum values in each row and column, the algorithm exposes zero-cost opportunities that can be covered by a minimum number of lines. When the minimum number of lines required to cover all zeroes equals the dimension of the matrix, an optimal assignment has been reached. This deterministic mathematical model ensures that exactly one worker is paired with exactly one task, preventing resource conflicts while minimizing the overall system cost.
The Mathematical Foundations of Bipartite Matching
The assignment problem models a complete weighted bipartite graph. In this graph, one side contains workers, machines, agents, or other resources, while the other side contains tasks, jobs, locations, or choices. Every matrix cell represents the cost of one possible pairing. A valid solution selects exactly one cell from every row and exactly one from every column. As documented by Google OR-Tools — Assignment, the primary goal is minimizing total assignment cost while preventing two workers from taking the same task.
Because the Hungarian algorithm runs in cubic time for an n by n matrix, it is highly efficient compared to brute-force enumeration of all possible permutations, which grows factorially. This mathematical baseline is highly versatile, but it is structurally distinct from other network optimization problems. For instance, while the assignment problem pairs discrete nodes on a bipartite graph, a minimum spanning tree connects all nodes in a general graph with the lowest total edge weight. If you are working on broader network designs, you can explore our guide on how to solve a minimum spanning tree problem to compare these optimization techniques.
Manual Matrix Reduction with a 3 by 3 Example
To understand the mechanics of the Hungarian method, it is helpful to walk through a manual calculation using a standard 3 by 3 matrix. In this scenario, we have three workers (W1, W2, W3) and three tasks (Task A, Task B, Task C). Our goal is to find the pairing that yields the absolute minimum total cost.
| Worker | Task A Cost | Task B Cost | Task C Cost |
|---|---|---|---|
| W1 | 2 | 3 | 3 |
| W2 | 3 | 2 | 3 |
| W3 | 3 | 3 | 1 |
To solve this by hand, follow the classic matrix reduction steps:
Step 1: Row Reduction
Identify the minimum value in each row and subtract it from every element in that row. This step creates at least one zero in each row.
- Row 1 minimum is 2. Subtract 2 from each cell: $[2-2, 3-2, 3-2] = [0, 1, 1]$
- Row 2 minimum is 2. Subtract 2 from each cell: $[3-2, 2-2, 3-2] = [1, 0, 1]$
- Row 3 minimum is 1. Subtract 1 from each cell: $[3-1, 3-1, 1-1] = [2, 2, 0]$
Step 2: Column Reduction
Using the row-reduced matrix, identify the minimum value in each column and subtract it from every element in that column. This ensures every column also contains at least one zero.
- Column 1 values are $[0, 1, 2]$. The minimum is 0. Subtracting 0 leaves the column unchanged: $[0, 1, 2]$
- Column 2 values are $[1, 0, 2]$. The minimum is 0. Subtracting 0 leaves the column unchanged: $[1, 0, 2]$
- Column 3 values are $[1, 1, 0]$. The minimum is 0. Subtracting 0 leaves the column unchanged: $[1, 1, 0]$
Step 3: Cover All Zeroes with the Minimum Number of Lines
Attempt to cover all the zeroes in the reduced matrix using the minimum number of horizontal or vertical lines. In our reduced matrix, the zeroes are located at (W1, Task A), (W2, Task B), and (W3, Task C). To cover these three independent zeroes, we must draw exactly three lines (either three rows or three columns).
Because the minimum number of lines required to cover all zeroes (3) is equal to the dimension of our matrix ($n = 3$), we have reached the optimal state. If the number of lines had been less than 3, we would have had to perform an additional iteration by finding the smallest uncovered element, subtracting it from all uncovered elements, and adding it to elements at line intersections.
Step 4: Determine the Optimal Assignment
We assign the workers to the tasks corresponding to the zero-cost cells in our fully reduced matrix:
- W1 is assigned to Task A (Original cost = 2)
- W2 is assigned to Task B (Original cost = 2)
- W3 is assigned to Task C (Original cost = 1)
To find the minimum total cost, we sum the original values of these optimal pairings: $2 + 2 + 1 = 5$. This matches the deterministic minimum-cost baseline for this standard 3 by 3 example.
How to Solve the Assignment Problem Online
While manual reduction is simple for a 3 by 3 matrix, larger matrices quickly become tedious and prone to arithmetic mistakes. The online Assignment Problem Solver automates this entire process. It parses a complete square matrix of 1 to 20 uniquely named workers and tasks, validates your inputs, and applies the primal-dual Hungarian algorithm to return the exact minimum-cost matching instantly.
- Write a header beginning with a comma followed by unique task names.
- Add one worker per row with exactly one finite cost for every task, keeping worker and task counts equal.
- Run the Hungarian solver, inspect each pairing and cost convention, then copy the exact minimum-cost assignment.
For example, to solve the 3 by 3 problem we calculated manually, you would paste the following comma-separated matrix into the input field:
,Task A,Task B,Task C W1,2,3,3 W2,3,2,3 W3,3,3,1
The tool runs entirely in your browser. It instantly displays each worker's assigned task, the individual pairing cost, and the total minimum cost. You can copy the final assignment table as plain text to use in your reports or homework assignments.
Understanding Model Assumptions and Boundaries
To use the Hungarian method successfully, your data must align with the mathematical assumptions of the model. The table below outlines how the manual method compares to the capabilities of the online solver tool, highlighting crucial structural boundaries.
| Feature or Constraint | Manual Hungarian Method | Online Solver Tool |
|---|---|---|
| Practical Matrix Size Limit | Typically up to 4x4 or 5x5 before manual errors skyrocket. | Up to 20x20, which easily covers classroom and modest scheduling tasks. |
| Processing Location | Your desk or whiteboard. | Locally in your browser; no data is uploaded to a server. |
| Input Validation | Subject to human oversight; easy to miss duplicate names or missing cells. | Rejects malformed or rectangular matrices, duplicate names, blanks, and NaN. |
| Tie Resolution | Resolved arbitrarily by the person drawing the lines. | Resolved deterministically using natural row and column order. |
| Cost Type Support | Supports any real numbers, but negatives complicate manual arithmetic. | Supports positive, zero, and negative values as long as they are finite. |
It is critical to remember that this solver always minimizes the numeric sum. If your data contains profits or scores that you want to maximize, you must transform them deliberately before pasting them into the tool. For example, you can subtract every value from the maximum value in your original matrix to turn a maximization problem into a minimization problem. Do not paste raw profit scores and assume that the "best" result automatically means the largest number.
Additionally, this implementation assumes that every worker is capable of performing every task. Blank or forbidden pairings are not supported as missing cells. If a pairing is physically impossible in your real-world scenario, you must assign it an exceptionally high dummy cost (a "penalty cost") to ensure the algorithm avoids selecting it.
Finally, the exact optimum generated by this model covers only the exact costs you enter. It does not account for real-world nuances such as skill thresholds, workload capacity, team dependencies, fairness, travel time changes, precedence, multiple tasks per worker, worker availability, or uncertainty. Real staffing decisions often involve legal, ethical, and human considerations that cannot be reduced to a cost matrix. Treat the mathematical result as a transparent baseline rather than an automatic, unreviewable personnel decision. For massive industrial schedules or highly constrained operations, you should use a validated mixed-integer, constraint-programming, or min-cost-flow solver that explicitly represents all policy rules.