An office has five technicians and five jobs to do today. Not every technician can do everything: one is certified for electrical systems, another knows a certain piece of software, another can drive the van. How many jobs can be covered, at most, by giving each technician a single job? And if every technician-job pair had a cost, for example travel time, which assignment would minimise the total?
These are two classic problems: maximum matching in a bipartite graph and the assignment problem.
The model
We build a bipartite graph: technicians on one side, jobs on the other, with an edge between a technician and a job when the pairing is possible. A matching is a set of edges with no endpoints in common: each technician and each job appears at most once. A matching is:
- maximal if no edge can be added;
- maximum if it has the largest possible number of edges;
- perfect if it covers every vertex.
Beware of the difference between maximal and maximum. A greedy approach, pairing each technician with the first free job, produces a maximal matching, which can be much smaller than the maximum. If Anna takes the only job Bruno could also do, and Bruno can do nothing else, the greedy choice leaves Bruno without work even though a better solution existed.
Augmenting paths
Given a matching, an alternating path uses edges outside and inside the matching in turn. If an alternating path starts and ends at free vertices, it is called an augmenting path: swapping the edges along the path (those outside go in, those inside come out) grows the matching by one.
Berge's theorem says that a matching is maximum if and only if it admits no augmenting paths. The basic algorithm is therefore: while you can find an augmenting path, use it.
def maximum_matching(adj, n_left, n_right):
matched_to = [-1] * n_right
def try_assign(u, seen):
for v in adj[u]:
if v in seen:
continue
seen.add(v)
if matched_to[v] == -1 or try_assign(matched_to[v], seen):
matched_to[v] = u
return True
return False
return sum(try_assign(u, set()) for u in range(n_left))
The try_assign function tries to place technician u: if job v is free, it takes it; if it is taken, it recursively asks the current technician to move to another job. The cost is proportional to n · m. The Hopcroft-Karp algorithm, which looks for many disjoint augmenting paths at once, brings it down to roughly m · √n.
The same result can be obtained with maximum flow: connect a source to all technicians and all jobs to a sink, with capacity 1 everywhere. The integral maximum flow corresponds to the maximum matching.
König's theorem
In bipartite graphs a useful equality holds: the size of the maximum matching equals the size of the minimum vertex cover, that is, the smallest set of vertices touching every edge. In practical terms: if the maximum matching is 4, there is a group of 4 people or tasks that «explains» why you cannot do better. This set is obtained from the last failed attempt to find augmenting paths, and it is an excellent tool for showing planners where the constraint lies.
Weighted assignment
If every technician-job pair has a cost and you want a perfect matching of minimum total cost, you have the assignment problem. Trying every combination is impossible even for modest sizes: with 10 technicians there are 10!, that is 3,628,800, possible assignments, and with 20 there are more than two billion billion.
The Hungarian method, presented by Harold Kuhn in 1955, solves the problem in polynomial time, proportional to n³ in its efficient version. It works on the cost matrix with a simple idea: subtracting a constant from a row or a column does not change which assignment is optimal, because every assignment uses exactly one element per row and per column.
The essential steps, in the matrix version:
- subtract from each row its minimum;
- subtract from each column its minimum;
- look for an assignment that uses only zero-cost cells;
- if none exists, cover all zeros with the minimum number of rows and columns, subtract the smallest uncovered value from the uncovered cells, add it to the cells covered twice and go back to step 3.
| Job 1 | Job 2 | Job 3 | |
|---|---|---|---|
| Anna | 4 | 2 | 8 |
| Bruno | 4 | 3 | 7 |
| Carla | 3 | 1 | 6 |
After the row and column reduction you find, for example, Anna → 2, Bruno → 3, Carla → 1, with cost 2 + 7 + 3 = 12. In this case other assignments have the same minimum cost, such as Anna → 1, Bruno → 3, Carla → 2: the method returns one of them.
Practical cases
- Shifts and staff: who covers which shift, respecting skills and preferences expressed as costs.
- Logistics: which vehicle goes to which customer to minimise empty kilometres.
- Tracking: in vision systems, matching the objects detected in one frame to those in the previous frame while minimising displacement.
- Document review: assigning reviewers to files while avoiding conflicts of interest, which are modelled simply by removing the forbidden edges.
In short
- A matching pairs elements of two groups without using any element twice.
- Greedy choices give maximal matchings but not always maximum ones.
- Augmenting paths, or a reduction to maximum flow, find the maximum matching.
- König's theorem links the maximum matching to the minimum vertex cover.
- The Hungarian method solves minimum-cost assignment in n³ time.
