Bipartite Matching & Assignment Problem
The assignment problem is exactly a minimum-weight perfect matching problem in a bipartite graph. This viewpoint explains why the Hungarian (Kuhn–Munkres) algorithm works and clarifies related variants: maximum matching, min-cost matching, and unbalanced cases (dummy nodes).
For the matrix-based algorithm steps, see Hungarian algorithm explained. For solved practice matrices, see assignment problem examples.
On this page
Quick takeaway: Workers and jobs form two disjoint node sets. Each edge has a cost. Choosing one edge incident to each worker and job (no conflicts) is a perfect matching. Minimizing its total cost is the assignment problem.
Core definitions (bipartite graph, matching, perfect)
Bipartite graph
A graph whose vertices can be split into two sets (left and right) such that every edge connects a left vertex to a right vertex.
Matching
A set of edges with no shared endpoints (no node is used twice).
Perfect matching
A matching that covers every vertex (each vertex is incident to exactly one selected edge). In an n×n assignment,
we want a perfect matching of size n.
If your matrix is not square, you typically add dummy nodes to recover a perfect matching interpretation: unbalanced assignment problem.
Map a cost matrix → bipartite graph
Given costs c(i,j):
- Left set = workers (W1…Wn)
- Right set = jobs (J1…Jn)
- Add an edge
(Wi, Jj)with weightc(i,j)for each allowed pair
The assignment is to choose n edges so that every worker and job is used once.
The matrix-based implementation of this idea is the Hungarian algorithm.
Minimum-weight perfect matching = assignment
In graph terms, the assignment objective “minimize total cost” is:
minimize Σ_(Wi,Jj in matching) weight(Wi,Jj) subject to matching is perfect
This explains two common confusions:
- Maximum matching (largest number of edges) is not the same as minimum-weight perfect matching.
- You can have a maximum matching without having a perfect matching (if the graph is missing edges).
If your problem is “one-to-one,” assignment is the right model. If it’s “ship quantities,” it’s transportation: assignment vs transportation.
Worked examples
Worked example
Example 1: Convert a 3×3 matrix to a matching and compute total cost
Cost matrix:
J1 J2 J3 W1 4 1 3 W2 2 0 5 W3 3 2 2
Graph view
Create edges from each worker to each job with the given weights. A perfect matching must choose 3 edges, one incident to each worker and each job.
One minimum-cost perfect matching
- W1—J2 (1)
- W2—J1 (2)
- W3—J3 (2)
Total cost = 1 + 2 + 2 = 5.
Hungarian finds this using zeros/reduced costs: Hungarian algorithm explained.
Worked example
Example 2: Missing edges → maximum matching but not perfect matching
Suppose W2 cannot do J2 and W3 cannot do J1 (edges missing). Then some perfect matchings may not exist at all. In that case:
- You may only be able to match 2 pairs (maximum matching size 2), not 3.
- To keep an assignment model, you can add a dummy node (interpreting “unmatched”) or use penalties.
For the standard dummy approach: unbalanced assignment.
Worked example
Example 3: Unbalanced case as matching with dummy nodes
If you have 3 workers and 4 jobs, add one dummy worker node so you can still talk about a perfect matching. Any job matched to the dummy worker is interpreted as “unfilled job.”
Full step-by-step dummy setup is on: unbalanced assignment problem.
Algorithms you’ll see (Hungarian, Hopcroft–Karp)
Hungarian / Kuhn–Munkres
Solves minimum-weight perfect matching in bipartite graphs (assignment). In matrix form it’s the Hungarian algorithm: step-by-step guide.
Hopcroft–Karp
Solves maximum cardinality matching in bipartite graphs (ignores weights). That’s useful when your goal is “match as many pairs as possible,” not “minimize cost.”
If you need weighted matching in code, see: Hungarian algorithm in Python (SciPy).
Questions people ask
Questions people ask
What is the difference between matching and assignment?
“Matching” is a graph concept (choose non-conflicting edges). “Assignment” is the OR/optimization formulation of minimum-weight perfect matching with one-to-one constraints.
Questions people ask
What does “perfect matching” mean in assignment?
It means every worker and every job is matched exactly once (balanced one-to-one assignment).
Questions people ask
Why does Hungarian algorithm work on zeros?
Zeros represent tight reduced costs under feasible dual potentials. A perfect matching among zeros corresponds to optimality (complementary slackness). See the dual explanation in Hungarian algorithm explained.
Questions people ask
Can there be more than one minimum-weight perfect matching?
Yes. Multiple matchings can tie for minimum total cost, especially when many reduced-cost zeros exist.
Questions people ask
What if the bipartite graph is not complete?
A perfect matching may not exist. You can (1) add dummy nodes (unbalanced form), (2) add penalties, or (3) solve a broader ILP/MILP depending on meaning.
What to do next
- Matrix method: Hungarian algorithm explained.
- Solved matrices: assignment examples.
- Unbalanced/dummies: unbalanced assignment.
- Python: Hungarian in Python (SciPy).
Disclaimer
This content is for education only. Real matching/assignment applications can include constraints not captured by perfect matching (capacities, multi-period decisions, fairness rules, precedence, forbidden pairs, or costs that depend on pairs of assignments such as QAP). Validate model assumptions and results before using them operationally. Read the full disclaimer.