liveBook · Manning

Hungarian algorithm

As explained in Algorithms Every Programmer Should Know

The Hungarian algorithm is a polynomial-time optimization procedure for finding a minimum-cost one-to-one assignment between two equally sized sets.

The Hungarian algorithm finds a minimum-cost one-to-one assignment, such as matching workers to tasks. It uses a square cost matrix: rows represent workers, columns represent tasks, and each cell records a pairing’s cost. section 3.0 section 3.1

The core procedure turns the assignment into a sequence of manageable checks:

  • Subtract each row’s minimum from every value in that row, then do the same for each column. section 3.1
  • Cover every zero with the fewest horizontal or vertical lines. If the number of lines equals the matrix size, select independent zeroes for the assignments. section 3.1 section 3.4
  • If fewer lines are needed, subtract the smallest uncovered value from uncovered cells and add it at line intersections; repeat the check. section 3.4

Matching cleaners to rooms

For three cleaners and three rooms, the resulting assignment gives Bob the kitchen, Carol the windows, and Alice the floors, for a total cost of $27. section 3.1

Trying every permutation takes factorial time; the Hungarian algorithm reduces the work to O(n³). It is useful for one-to-one matching, though production settings may require variations when the numbers of workers and tasks differ. section 3.0 section 3.2

Figure 3.1 Cost matrix is created with the rows representing the workers and the columns representing the tasks. The values in the matrix denote the cost to complete the task. The cost can be replaced by other factors based on the use case like time taken, amount of work, or any other measurable value.

Use the cost-matrix figure to see how workers, tasks, and pairing costs map to rows, columns, and cells. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces row and column reductions, zero-cover tests, matrix adjustments, assignment selection, and O(n³) complexity.
Examples
Works through a cleaner-to-room cost matrix and a developer-to-module hours matrix.
What you can do after
Apply minimum-cost assignment with SciPy's linear_sum_assignment and calculate the resulting total cost.
How it connects
Connects the assignment problem to bipartite graphs and the linear sum assignment problem.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.