liveBook · Manning

Cost matrix

As explained in Algorithms Every Programmer Should Know

A cost matrix records the cost of each possible worker–task assignment in a row-and-column table.

A cost matrix lays out the cost of each possible worker–task pairing: rows represent workers, columns represent tasks, and each cell gives the cost of one assignment. The Hungarian algorithm uses this table to find a minimum-cost one-to-one matching. section 3.0

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.

The figure shows how worker and task labels map to the rows and columns, and how each cell can hold a measurable assignment value. section 3.1

A small cost matrix makes the idea concrete:

  • For three cleaners and three jobs, the entries are cleaning rates. The algorithm’s final pairings assign Alice to Floors, Bob to Kitchen, and Carol to Windows, for a total cost of 27 dollars. section 3.1
  • The entries can also measure hours, such as the time developers need to complete software modules, or other measurable factors suited to the allocation problem. section 3.1

For the balanced case, the matrix is square, with the same number of workers and tasks. The Hungarian algorithm subtracts row and column minima to reveal zero-cost opportunities, then adjusts the matrix when those opportunities do not yet allow a complete assignment. section 3.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines a square worker-by-task table and traces reductions, zero-cover checks, and matrix adjustments until assignments can be selected.
Examples
Uses cleaner rates and developer-module hours, then applies matching to airline crews and cloud jobs.
What you can do after
Apply it via the Hungarian algorithm or SciPy's linear_sum_assignment to represent costs and obtain a minimum-cost pairing.
How it connects
Connects to the assignment problem, Hungarian algorithm, and linear sum assignment.

Also explained in

Compare how 2 books explain cost matrix →

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.