liveBook · Manning

Assignment problem

As explained in Algorithms Every Programmer Should Know

The assignment problem allocates agents to tasks, typically one-to-one, to optimize an objective such as total cost.

The assignment problem pairs workers with tasks to minimize total cost. In the balanced case, each worker gets one task and the cost matrix is square. section 3.0 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.

A cost matrix places workers in rows and tasks in columns; its values can represent costs or other measurable factors. section 3.1

The Hungarian algorithm improves on checking every possible pairing:

  • Subtract each row's minimum, then each column's minimum. section 3.4
  • Cover the zeroes with the fewest lines. If fewer than n lines suffice, adjust uncovered and intersecting cells and repeat. section 3.4
  • When n lines are needed, select independent zeroes for the assignments and use the original costs to calculate the total. section 3.4

A worker-task match

One solution assigns Alice to Floors, Bob to Kitchen, and Carol to Windows, for a total cost of 27. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through reductions, zero-covering lines, matrix adjustment, and assignment selection; contrasts O(n³) with O(n!).
Examples
Uses chores, worker-task costs, developer-module hours, crew scheduling, and server job placement.
What it assumes
Starts with workers, tasks, and measurable pairwise costs, then demonstrates the balanced square case.
What you can do after
Apply the problem with SciPy's linear_sum_assignment to obtain worker-task matches and their total cost.
How it connects
Connects assignment problems to the Hungarian algorithm, linear sum assignment, and crew or job scheduling.

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.