liveBook · Manning

Optimal assignment

As explained in Algorithms Every Programmer Should Know

An optimal assignment is a one-to-one assignment whose total cost is minimum among all feasible assignments.

An optimal assignment pairs workers with distinct tasks so the sum of their measurable costs is as small as possible. A cost matrix records the cost of each possible pairing. section 3.1

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.

Read each row as a worker, each column as a task, and each cell as the cost of that pairing. section 3.1

The Hungarian method works toward a set of non-overlapping zero-cost pairings:

  • Subtract each row’s minimum from its entries, then do the same for each column. section 3.1
  • Cover all zeros with the fewest horizontal or vertical lines. If the line count equals the matrix size, a one-to-one assignment is possible; otherwise, adjust the matrix using the smallest uncovered value and repeat. section 3.1

Matching people to jobs

For apartment cleaning, Alice is assigned floors for $10, Bob the kitchen for $9, and Carol the windows for $8: $27 total. The same approach can assign developers to software modules using estimated hours as costs. section 3.1

For implementation, SciPy provides `linear_sum_assignment`; the described implementation uses Jonker–Volgenant internally. The method’s stated time complexity is O(n³), which can make larger problems costly. section 3.1 section 3.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces row and column reductions, zero-cover tests, and matrix adjustments, then notes cubic scaling without deriving it.
Examples
Uses apartment-cleaning assignments and developer-to-module estimates to illustrate minimum-cost matching.
What you can do after
Apply via SciPy’s `linear_sum_assignment` to obtain worker-task pairs and their total cost.
How it connects
Connects cost matrices to bipartite graphs and the linear sum assignment problem, and discusses Hungarian and Jonker–Volgenant algorithms.

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.