Lesson 5 of 7 · 15 min

Allocation problems and bipartite graphs

Represent an allocation problem as a bipartite graph and as a table or matrix, then find the best allocation of a small problem by inspection.

What you will be able to do

  • Draw a bipartite graph for an allocation problem and write it as a table or matrix.
  • Find every possible allocation when only some people can do some tasks.
  • Find the minimum or maximum total for a 3×33 \times 3 problem by listing all the allocations.
  • Explain why inspection becomes impractical for larger problems.

Four volunteers have put their hands up for the school fete, and four stalls need running. Each volunteer can run exactly one stall, each stall needs exactly one volunteer, and not everyone can do everything. Who should go where?

This is an allocation (or assignment) problem: match each member of one group with exactly one member of another.

Definition

Allocation problems and bipartite graphs

An allocation problem has two groups — such as people and tasks — of the same size. A bipartite graph shows it: the people are one set of vertices, the tasks are the other, and an edge joins a person to each task they could do. Edges never join two people or two tasks.

An allocation (or assignment) picks one edge at each vertex, so every person gets exactly one task and every task exactly one person.

Which stalls each volunteer can run.

Worked example

Finding an allocation from a bipartite graph

  • Foundation

The bipartite graph in the lesson shows which fete stalls each volunteer can run: Kai can run the Barbecue or the Gate; Lena only the Canteen; Mia the Barbecue, the Canteen or the Raffle; Noah only the Gate.

Find an allocation in which every volunteer runs exactly one stall and every stall has a volunteer. Is it the only one?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Allocate any person (or task) with only one possible partner.

  2. Cross off what is taken and repeat.

  3. If you ever have a free choice, try each option to find every allocation.

Suppose Noah could run the Raffle as well as the Gate, and nothing else changes. How many complete allocations would there be?

Choose one answer

Often every person can do every task, but some pairings are better than others. Then each edge of the bipartite graph carries a weight — a cost, a time, a distance or a score — and the same information fits neatly in a table.

Time in minutes for each technician to do each repair job, as a weighted bipartite graph.

The same times as a table. Row: technician. Column: job.
TechnicianJob 1Job 2Job 3
Ari1267
Bea111314
Cam8812
The cost matrix: the entry in row ii, column jj is the time for technician ii to do job jj.
[12671113148812]\begin{bmatrix} 12 & 6 & 7 \\ 11 & 13 & 14 \\ 8 & 8 & 12 \end{bmatrix}

Worked example

The quickest allocation by listing every possibility

  • Simple familiar

Three technicians, Ari, Bea and Cam, each quote a time in minutes to do three repair jobs.

Job 1Job 2Job 3
Ari1267
Bea111314
Cam8812

Each technician does one job. By inspection, find the allocation that gives the smallest total time.

3 steps

Try it yourself first, then check the working one step at a time.

Method

  1. List every allocation systematically (n!n! of them).

  2. Total each one.

  3. Choose the smallest (or largest) total, and check whether more than one allocation gives it.

Watch out for

  • Giving Ari the quickest job (Job 2, 6 minutes) first. The best allocation gives Ari Job 3, because Bea is so much better at Job 1 than at Jobs 2 and 3.

Suppose the table above showed points the technicians earn for each job instead of minutes, and the manager wanted the largest total. What is the maximum total?

Common mistake

Choosing greedily

Giving each person their cheapest task in turn does not guarantee the best total. Ari's quickest job is Job 2 (6 min); then Bea's quickest remaining job is Job 1 (11 min), leaving Cam with Job 3 (12 min). That totals 29 minutes, but the optimum is 26.

Note

Why inspection runs out of steam

With nn people and nn tasks there are n×(n−1)×⋯×1=n!n \times (n - 1) \times \dots \times 1 = n! allocations: 6 for three people, 24 for four and 120 for five. Listing them all is fine for 3×33 \times 3, slow for 4×44 \times 4 and hopeless by hand for 5×55 \times 5. The next lesson gives a method that avoids the list.

How many different complete allocations are there of 4 workers to 4 jobs, one job each?

Summary

  • An allocation problem matches each member of one group with exactly one member of another.

  • A bipartite graph shows which pairings are possible; weights show their cost, time or score.

  • The same weights in a table or matrix: one row per person, one column per task.

  • For small problems, list every allocation systematically and choose the smallest (or largest) total.

  • There are n!n! allocations, so inspection suits only small problems; greedy choices can miss the optimum.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 5 of 70% read

Save your progress with a free account