The assignment problem in operational research is solved exactly in O(n³) time by the Hungarian algorithm, which selects one cell from every row and exactly one from every column of a square cost matrix so that the summed cost is provably minimal.
The assignment problem is one of the cleanest entry points to combinatorial optimization in an operational research course. It models any situation in which you must give every worker exactly one task and every task exactly one worker, while minimizing total cost, time, or distance. The classic classroom examples are assigning contractors to projects, repair crews to breakdowns, or machines to production runs. Because the cost matrix is square and complete — every worker can take every task with a known finite cost — the problem is a special case of the transportation problem in which supply, demand, and the number of suppliers all equal the number of tasks. The Hungarian algorithm, introduced by Harold Kuhn in 1955 and also known as the Kuhn–Munkres method, returns that exact minimum in cubic time. A browser implementation such as the Assignment Problem Solver produces the pairing and total immediately from the matrix, which is useful both for verifying a hand calculation and for sizing a small draft schedule.
The Assignment Problem as an Operations Research Model
Operational research treats the assignment problem as a binary linear program. Let xᵢⱼ be a binary variable that equals 1 when worker i is paired with task j and 0 otherwise. The objective is to minimize the total cost Σᵢ Σⱼ cᵢⱼ xᵢⱼ over every (i, j), where cᵢⱼ is the cost of that particular pairing. Two sets of constraints enforce the one-to-one rule: every worker appears in exactly one pairing (Σⱼ xᵢⱼ = 1 for each i), and every task is taken by exactly one worker (Σᵢ xᵢⱼ = 1 for each j). The number of workers must equal the number of tasks for these two constraint sets to be consistent with a square matrix; otherwise the system either over-assigns or leaves a row unmatched.
The same model reads naturally as a graph problem. Draw workers on one side of a bipartite graph and tasks on the other, then draw a weighted edge between every worker and every task whose weight is the cost of pairing them. The matrix is the weighted adjacency matrix of the complete bipartite graph K_{n,n}, and a feasible assignment is a perfect matching — one edge incident to every vertex. A minimum-cost assignment is therefore a minimum-weight perfect matching in a complete bipartite graph. Google OR-Tools describes this dual reading as minimizing total assignment cost while preventing two workers from taking the same task, which is the same condition written out in plain English.
Why the Hungarian Algorithm Solves It in Polynomial Time
Brute force is not a realistic method for the assignment problem. Enumerating every permutation of n workers already costs n! comparisons, which is infeasible beyond roughly n = 10. The Hungarian algorithm replaces enumeration with a sequence of augmentations that converges in polynomial time. It maintains two arrays of potentials, one for rows and one for columns, and repeatedly augments a minimum reduced-cost matching until every row is incorporated. Each iteration either assigns a new row to a free column or adjusts the potentials so that a previously infeasible assignment becomes feasible without ever raising the cost.
Kuhn's 1955 paper established that the algorithm terminates in cubic time for an n×n matrix. Three nested passes are enough: one over rows, one over columns, and one to find the augmenting path inside the current equality subgraph. Because the method is exact and deterministic — natural row and column order resolves ties when several assignments share the same total cost — the same matrix always returns the same pairing and the same minimum total. A step-by-step worked view of the row and column reductions lives in the guide Solve Assignment Problem by Hungarian Method; the worked matrix below focuses on the input format and the verified numerical result.
How to Enter the Cost Matrix and Read the Result
- Write a header beginning with a comma followed by unique task names. A three-task example begins with the empty top-left field followed by ",Task A,Task B,Task C", so each task occupies one column.
- Add one worker per row with exactly one finite cost for every task, keeping worker and task counts equal. The first column of each data row holds the worker's name; every subsequent column holds a single finite cost for that worker–task pair. Names must be unique within their side and counts must match the number of task columns.
- Run the Hungarian solver, inspect each pairing and cost convention, then copy the exact minimum-cost assignment. The result lists one task per worker, the cost of that pairing, and the minimum total. Copy the output as text to paste into a report, a comparison column, or a verified answer sheet.
A 3×3 Worked Example
Consider three workers (W1, W2, W3) and three tasks (A, B, C) with the following comma-separated cost matrix. The empty top-left cell is intentional and signals that the first row is a header rather than a data row.
| Worker | Task A | Task B | Task C |
|---|---|---|---|
| W1 | 3 | 1 | 4 |
| W2 | 2 | 4 | 1 |
| W3 | 4 | 3 | 2 |
The optimal pairing under the Hungarian algorithm assigns W1 to Task B, W2 to Task A, and W3 to Task C. The formula is the sum of the selected cells:
Total cost = c(W1, B) + c(W2, A) + c(W3, C) = 1 + 2 + 2 = 5.
To confirm that 5 is the minimum and not just a low value, compare it with one alternative pairing such as W1→A, W2→B, W3→C, which gives 3 + 4 + 2 = 9. Every other permutation of the three workers yields a sum of at least 5, so 5 is the exact minimum for this matrix. The browser tool returns the same pairing and the same total because the algorithm is deterministic.
How Different Solver Approaches Compare
The Hungarian algorithm is the canonical polynomial-time method for this exact model, but operational research offers other ways to frame the same problem depending on the constraints you actually need.
| Approach | Model scope | Key strength | Key limit |
|---|---|---|---|
| Hungarian algorithm | Complete square cost matrix | Polynomial-time exact, deterministic output | No forbidden cells, no per-worker capacity |
| Transportation formulation | Same square matrix, treated as a balanced transportation problem | Reuses the classical transportation simplex | Same structural limits as Hungarian |
| Mixed-integer linear program (MILP) | Any size, any linear constraints | Supports forbidden cells, capacity, multi-task per worker, and side constraints | Requires an external solver; runtime depends on the instance |
The browser tool implements the first row of this table. For the second and third rows you would normally hand the matrix to a dedicated solver library or a modelling package such as a constraint-programming or min-cost-flow system.
Where the Mathematical Model Stops
The exact minimum covers only the costs you entered. It does not, on its own, encode skill thresholds, workload capacity, team dependencies, fairness, travel-time changes, precedence between tasks, multiple tasks per worker, worker availability, or uncertainty unless those effects are already represented correctly in the cost matrix. A negative cost can represent a benefit, but only if that sign convention genuinely fits your model — the solver always minimizes the numeric sum, so a profit-to-maximize problem must be transformed deliberately or solved with a maximization model rather than pasted in as a score.
Real staffing decisions also involve legal, ethical, and human considerations that cannot be reduced to a cost matrix. Treat the result as a transparent mathematical baseline, not an automatic personnel decision. For larger or constrained schedules — say more than twenty workers, restricted pairings, or capacity limits — use a validated mixed-integer, constraint-programming, or min-cost-flow solver that explicitly represents every rule, then independently review the final assignment before acting.
Verifying a Hand Calculation Against the Tool
Because the algorithm is deterministic, the same matrix always produces the same pairing. That makes the Assignment Problem Solver useful as a transparent baseline in three common situations: verifying a homework answer against a manual Hungarian walk-through, comparing two slightly different cost matrices to see which assumption actually changes the assignment, and allocating a small set of machines to jobs in a draft schedule where every cost is known. Everything runs locally in the browser, so you can paste a labelled matrix, read the result, and copy it as text without uploading your data to a remote service.
When the tool rejects the matrix visibly, the most common reasons are a non-square shape, duplicate row or column names, blanks where a number was expected, NaN entries, or infinite costs. Correcting those inputs is usually enough to recover the exact minimum and confirm your hand calculation.