12.11 Assignment Problem
In maximum bipartite matching, every assignment has the same value.
12.11 Assignment Problem
Problem
In maximum bipartite matching, every assignment has the same value. The goal is simply to maximize the number of matches.
Many real-world allocation problems are more complicated. Every assignment has a cost, profit, distance, or score.
Consider assigning workers to jobs:
| Worker | Job A | Job B | Job C |
|---|---|---|---|
| Alice | 8 | 2 | 7 |
| Bob | 6 | 4 | 3 |
| Carol | 5 | 8 | 1 |
The numbers may represent:
- Time required
- Cost of execution
- Travel distance
- Resource consumption
A perfect matching exists, but not all perfect matchings are equally good.
The objective becomes:
Assign exactly one job to each worker while minimizing total cost.
This is known as the assignment problem.
Solution
Model the problem as a weighted bipartite graph.
Unlike ordinary matching, every edge now has a cost:
worker -> task
with:
cost(worker, task)
The goal is to find a perfect matching with minimum total cost.
Several approaches exist:
- Exhaustive search
- Dynamic programming
- Minimum-cost flow
- Hungarian algorithm
The Hungarian algorithm is the classical solution and solves the assignment problem in polynomial time.
Assignment as a Bipartite Graph
Consider:
| Worker | A | B | C |
|---|---|---|---|
| Alice | 8 | 2 | 7 |
| Bob | 6 | 4 | 3 |
| Carol | 5 | 8 | 1 |
Represent this as:
Alice ---- A (8)
Alice ---- B (2)
Alice ---- C (7)
Bob ------ A (6)
Bob ------ B (4)
Bob ------ C (3)
Carol ---- A (5)
Carol ---- B (8)
Carol ---- C (1)
Each edge contains a cost.
A matching chooses exactly one edge incident to each worker and each task.
Brute Force Approach
For three workers:
Possible assignments:
| Alice | Bob | Carol |
|---|---|---|
| A | B | C |
| A | C | B |
| B | A | C |
| B | C | A |
| C | A | B |
| C | B | A |
There are:
3! = 6
possibilities.
For:
n = 20
there are:
20!
possibilities.
Exhaustive search quickly becomes impossible.
Flow Interpretation
The assignment problem can be viewed as a minimum-cost flow problem.
Construct:
source
workers
tasks
sink
Network:
s -> workers
workers -> tasks
tasks -> t
Capacities:
1
on every edge.
Worker-task edges additionally receive costs.
A flow of:
n
units corresponds to a complete assignment.
The minimum-cost flow corresponds to the optimal assignment.
This formulation generalizes naturally to larger scheduling and allocation problems.
Example
Suppose we choose:
| Worker | Task | Cost |
|---|---|---|
| Alice | B | 2 |
| Bob | C | 3 |
| Carol | A | 5 |
Total:
2 + 3 + 5 = 10
Alternative assignment:
| Worker | Task | Cost |
|---|---|---|
| Alice | A | 8 |
| Bob | B | 4 |
| Carol | C | 1 |
Total:
8 + 4 + 1 = 13
The first assignment is better.
The assignment problem seeks the minimum such total.
Cost Matrix Representation
The standard representation is a square matrix:
| A | B | C | |
|---|---|---|---|
| Alice | 8 | 2 | 7 |
| Bob | 6 | 4 | 3 |
| Carol | 5 | 8 | 1 |
Rows represent workers.
Columns represent tasks.
Entry:
matrix[i][j]
represents assigning worker i to task j.
Most assignment algorithms operate directly on this matrix.
Hungarian Algorithm Intuition
The Hungarian algorithm transforms the matrix while preserving optimal solutions.
The key observation is:
Adding or subtracting the same constant from an entire row or column does not change which assignment is optimal.
Suppose:
| A | B | C | |
|---|---|---|---|
| Alice | 8 | 2 | 7 |
Subtract:
2
from the entire row:
| A | B | C | |
|---|---|---|---|
| Alice | 6 | 0 | 5 |
Every possible assignment involving Alice decreases by the same amount.
Relative quality remains unchanged.
This operation creates zeros that reveal promising assignments.
Row Reduction
For each row:
- Find minimum value.
- Subtract it from every entry.
Example:
| A | B | C | |
|---|---|---|---|
| Alice | 8 | 2 | 7 |
Minimum:
2
After reduction:
| A | B | C | |
|---|---|---|---|
| Alice | 6 | 0 | 5 |
Repeat for every row.
Column Reduction
After row reduction:
- Find minimum value in each column.
- Subtract it from that column.
Additional zeros appear.
These zeros represent assignments that can potentially belong to an optimal solution.
Zero Covering
The algorithm repeatedly:
- Covers all zeros using the minimum number of lines.
- Tests whether enough independent zeros exist.
- Modifies the matrix if necessary.
Eventually the zeros contain a complete assignment.
The details are somewhat involved, but the overall goal remains simple:
Create enough zero-cost candidate assignments
to build a perfect matching.
Small Example
Matrix:
| A | B | |
|---|---|---|
| Alice | 4 | 1 |
| Bob | 2 | 3 |
Row reduction:
| A | B | |
|---|---|---|
| Alice | 3 | 0 |
| Bob | 0 | 1 |
Column reduction changes nothing.
Independent zeros:
Alice -> B
Bob -> A
Assignment cost:
1 + 2 = 3
Optimal.
Assignment as Matching
The Hungarian algorithm can be viewed as repeatedly constructing matchings among zero-cost edges.
At a high level:
Transform costs
↓
Generate zeros
↓
Find matching
↓
Adjust matrix
↓
Repeat
This explains the close relationship between assignment and matching.
Practical Applications
Worker Scheduling
Assign employees to jobs while minimizing labor cost.
Vehicle Routing
Assign drivers to routes while minimizing travel distance.
Cloud Scheduling
Assign workloads to machines while minimizing resource consumption.
Manufacturing
Assign tasks to machines while minimizing completion time.
Sports Scheduling
Assign officials to games while minimizing travel.
Data Association
Assign observations to tracked objects while minimizing prediction error.
Complexity
For an:
n × n
cost matrix, the Hungarian algorithm runs in:
O(n³)
This is dramatically better than:
O(n!)
for brute force search.
For moderate values of n, the algorithm is extremely practical.
Hungarian vs Min-Cost Flow
| Technique | Strength |
|---|---|
| Hungarian | Pure assignment problems |
| Min-cost flow | More general constraints |
| Matching | Unweighted assignments |
| Dynamic programming | Small state spaces |
When every worker must receive exactly one task and every task exactly one worker, Hungarian is often the preferred choice.
When capacities, quotas, or additional constraints appear, minimum-cost flow becomes more flexible.
Common Mistakes
Solving Assignment as Matching
Ordinary matching ignores costs.
It may maximize the number of assignments but produce poor allocations.
Forgetting Square Matrices
The classical Hungarian algorithm assumes:
workers = tasks
Rectangular instances are usually padded with dummy rows or columns.
Confusing Cost and Profit
Maximum-profit problems can be converted into minimum-cost problems by subtracting profits from a large constant.
Ignoring Numerical Scale
Large costs may require 64-bit integers.
Discussion
The assignment problem is one of the most important examples of combinatorial optimization. It sits at the intersection of matching, flow, and linear programming. Many larger optimization systems contain assignment as a core subproblem.
The Hungarian algorithm remains a classic because it converts an apparently exponential search problem into a sequence of simple matrix transformations that reveal the optimal structure directly.
Takeaway
The assignment problem extends bipartite matching by attaching costs to assignments. Instead of maximizing the number of matches, the goal is to find a complete matching with minimum total cost.
The Hungarian algorithm solves this problem in O(n³) time and forms the foundation for many scheduling, allocation, routing, and optimization systems. The next recipe generalizes these ideas further by introducing minimum-cost maximum-flow, which combines flow constraints with optimization objectives.