Can the assignment objective maximize a score?

Yes, suitable formulations or cost transformations can express maximization.

Can multiple assignments share the minimum?

Yes; a separate tie-breaking rule may be needed.

Does the method train from examples?

No. It optimizes supplied costs, although a learned model can produce those costs.

AI Glossary / Graphs and symbolic AI / Advanced

Hungarian algorithm

Definition

The Hungarian algorithm solves a linear assignment problem by finding a one-to-one pairing with minimum total cost. In the standard square formulation, each worker receives exactly one task and each task exactly one worker. The objective adds the selected pairing costs.

What it means

An assignment problem contains two sets of objects and a cost for each permitted pairing. The objects may be detections and tracks, machines and jobs, or resources and locations.
The one-to-one rule couples decisions. Two workers may both prefer the same task, so selecting their individual minima can produce an invalid allocation. The algorithm finds a globally optimal combination for the stated cost matrix and assignment constraints. It does not establish that the costs correctly represent business priorities or that omitted constraints are satisfied.

How it works

A matrix version begins by subtracting each row's minimum from that row, then each column's minimum from that column. These operations preserve the optimal assignments in a square complete-assignment problem because every feasible assignment selects one entry per row and column.
Seek a complete assignment among the resulting zeros, with no repeated row or column. If none exists, cover all zeros with the fewest horizontal and vertical lines. Subtract the smallest uncovered value from uncovered entries and add it at intersections of two covering lines, leaving singly covered entries unchanged. Repeat until a complete zero assignment exists.
Use the selected positions in the original matrix to calculate the actual cost. Reduced zeros are an optimization device, not evidence that real assignments are free. Efficient implementations often express the same underlying ideas through labels, matching, and augmenting paths rather than hand-drawn lines.

Three practical examples

Task allocation: A planning tool pairs available technicians with independent jobs using estimated travel or completion costs. Certifications, time windows, and workload interactions must be handled explicitly rather than assumed to follow from a low total cost.
Object tracking: A vision system matches existing tracks to new detections using a cost based on compatibility. Missing detections and new objects require appropriate unmatched options; forcing every object into a pairing can produce incorrect identities.
Resource placement: A team assigns several interchangeable units to service locations using transport costs. If each location needs one unit and each unit serves one location, the basic formulation fits. Multi-unit demands require a different or expanded model.

Think of it this way

Imagine seating people at distinct assigned desks. Giving everyone their favorite desk fails when several choose the same one. The Hungarian algorithm considers the combination of choices, looking for the least costly complete seating arrangement under the supplied scores and rules.

Worked example

There are three workers A, B, and C and three tasks 1, 2, and 3. Costs are A: (6, 2, 7), B: (5, 3, 4), and C: (4, 8, 3). Every pairing is permitted, and the objective is the sum of the three selected costs.
Subtract row minima 2, 3, and 3. The rows become (4, 0, 5), (2, 0, 1), and (1, 5, 0). Next subtract column minima 1, 0, and 0, giving (3, 0, 5), (1, 0, 1), and (0, 5, 0).
A and B now both have their only zero in column 2, so a complete zero assignment is impossible. Cover the zeros using column 2 and row C. Two lines suffice, fewer than the required three independent assignments.
The smallest uncovered value is 1. Subtract it from uncovered entries and add it at the intersection of row C and column 2. The new rows are (2, 0, 4), (0, 0, 0), and (0, 6, 0).
Select A to task 2, B to task 1, and C to task 3. These are independent zeros. In the original costs, their total is 2 + 5 + 3 = 10. Another optimum is A to 2, B to 3, and C to 1, totaling 2 + 4 + 4 = 10.
For this example, enumerate all six possible assignments independently. Their totals are 12, 18, 10, 10, 20, and 14. The minimum is 10, confirming the result and showing that it is not unique. Enumeration verifies this small example but becomes impractical for large problems.

Illustrative case study

Fictional Cedar Assignments initially lets each team member select the cheapest remaining task in a fixed order. Managers discover that the result depends heavily on who chooses first and can overlook better complete combinations.
The team introduces a linear assignment model and checks it on small cases where every feasible allocation can be inspected. It also records unavailable pairings and distinguishes the total-cost objective from individual fairness requirements. Ties are resolved using an explicit secondary policy rather than treating the solver's output order as a business preference.
The revised process produces a defensible optimum for the modeled problem while keeping feasibility rules, cost estimation, and policy choices visible for review.

Common misconceptions and mistakes

“Selecting every row minimum solves the problem.” Those choices can reuse a task.
“A zero in the reduced matrix means no actual cost.” Original costs determine the reported total.
“The optimum is always unique.” The worked example has two optimal assignments.
“Minimum total cost minimizes the worst individual cost.” These are different objectives.
“Any assignment solver uses the Hungarian algorithm.” SciPy documents its current linear_sum_assignment implementation as a modified Jonker-Volgenant algorithm.

Business use

Confirm the one-to-one structure and additive cost assumption before selecting this method. Interactions between assignments, shared capacities, scheduling sequences, and mandatory group rules can require a more general optimization model.
For unequal set sizes, define which items may remain unmatched and what that means operationally. Dummy rows or columns can encode such choices in a square model, but their costs must reflect the intended policy. Verify that every returned pair is permitted and recalculate the total using the original data.

Check your understanding

Why do the first zeros not provide a complete assignment?

Answer: A and B both require column 2.

What is the original cost of A2, B1, C3?

Answer: It is 10.

Why might a mathematically optimal allocation be unsuitable?

Answer: Its model may omit a required constraint or use misleading costs.

Related terms

Assignment problems
Optimization
Assignment problem
bipartite matching
cost matrix
augmenting path
minimum-cost flow
tie-breaking

Learn next

Change one cost in the example and solve it again. Compare minimum total cost with a requirement to limit every worker's individual cost, noting when the original objective no longer answers the question.

Sources

Harvard mathematics teaching material, The Assignment Problem and the Hungarian Method: https://legacy-www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf SciPy, linear_sum_assignment problem definition and implementation distinction: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html

Previous: Human system integration Next: Hurdle model