Assignment and the Hungarian algorithm

Part 1

What the exam asks about assignment

Every external from 2020 to 2025 had an assignment question. I count nine: four multiple choice (2021 Paper 1 Question 5, 2022 Paper 1 Question 7, 2023 Paper 1 Question 13 and 2025 Paper 1 Question 10) and five short response worth 27 marks (2020 Paper 2 Question 5, 2021 Paper 2 Question 6, 2022 Paper 1 Question 20, 2023 Paper 2 Question 1 and 2024 Paper 2 Question 5).

Four of the five short-response questions sit in Paper 2, at 5 to 7 marks each, and every one is a single question with no parts. Nothing is broken into steps for you. Topic 5 as a whole, with flow networks, carried 45 short-response marks across the six papers. Flow networks have their own guide, Topic guide 14, Flow networks.

The multiple choice items have mostly gone well: on three of the four, 83.5% to 94.1% of students were right. The exception is 2022 Question 7, where only 57.1% could read the assignment off a finished matrix. Part 3 shows the routine that gets it right.

What the subject reports said

• •2020. The report showed an effective response to Paper 2 Question 5 to demonstrate “using a matrix method, as indicated within the question, to develop a response instead of by inspection”.
• •2021. Students “responded well to … using a bipartite graph to represent an assignment/allocation problem”. That is Paper 1 Question 5 (Part 2).
• •2022. Students responded well to “use of the Hungarian algorithm to determine an optimal assignment”, and the report asked for “using a new drawing to show the resultant matrix after applying each step of the Hungarian algorithm”.
• •2023 and 2024. Both reports asked for “separate matrices to show the outcome for each step”: row reduction, column reduction, and “continuing the algorithm until the minimum number of lines to cover all zeroes is equal to the number of assignments”.
• •2025. The report confirmed the syllabus change: “the required optimum assignment could be a minimum or a maximum, and using the Hungarian algorithm is expanded to 3 x 3 up to 5 x 5 square matrices.”

What the syllabus says

Unit 4 Topic 5, sub-topic “Assigning order and the Hungarian algorithm” (7 hours), has three dot points:

• •Use a bipartite graph and its tabular or matrix form to represent possible assignments for an allocation problem.
• •Determine the optimum (minimum and maximum) assignment/s for small-scale practical problems by inspection.
• •Use the Hungarian algorithm (3 × 3 up to 5 × 5 square matrices) to determine the optimum (minimum and maximum) assignment/s for larger practical problems.

Seven hours makes this one of the longer sub-topics in Unit 4 (three others get 8). Read “minimum and maximum” twice. Every optimisation question from 2020 to 2025 asked for a minimum, so the maximum is the part of this dot point nobody has met in an external yet. It has its own section in Part 6.

What the formula book gives you

So the steps of the algorithm are memory. The good news is that they are mechanical apart from two judgement points: covering the zeros with the fewest lines, and choosing one zero in each row and column. Parts 3 and 4 give you a routine for each.

Part 2

A bipartite graph and a matrix hold the same information

A bipartite graph has two groups of vertices. Every edge joins a vertex in one group to a vertex in the other, and no edge joins two vertices in the same group. Assignment problems are bipartite by nature: workers down one side, tasks down the other.

The matrix (or table) form holds the same information. Rows are one group, columns are the other, and each entry is the weight of the edge between them: a time, a distance, a cost. When the graph only shows who can do what, with no weights, the table simply lists each person’s possible tasks.

Solving by inspection

For an unweighted graph, look for a forced move. A vertex with only one edge must use it. Make that pairing, cross out both vertices, and look again. Most of these questions fall over in two or three moves.

For a weighted problem, inspection means checking the possible assignments and totalling them. A 3 × 3 has $3\times 2\times 1=6$ assignments, which you can list in a minute. A 4 × 4 has 24 and a 5 × 5 has 120. That is why the algorithm exists.

Part 3

Reduce the rows, reduce the columns, then read the zeros

The Hungarian algorithm works on a square matrix of costs and finds the assignment with the smallest total. Learn these steps in order.

1. 1Row reduction. Subtract the smallest value in each row from every entry in that row. Every row now has at least one zero.
2. 2Column reduction. Subtract the smallest value in each column from every entry in that column. Every column now has at least one zero.
3. 3Cover the zeros with the fewest possible straight lines, each through a whole row or a whole column. If the number of lines equals the size of the matrix, stop and assign (step 5). If there are fewer lines, go to step 4.
4. 4Adjust. Find the smallest uncovered value. Subtract it from every uncovered entry, add it to every entry covered twice, then go back to step 3. (Part 4.)
5. 5Assign. Choose one zero in each row and each column. Those positions are the optimal assignment. Add the original values in those positions for the total.

Why does it work? Every assignment uses exactly one entry from each row. Subtracting 17 from a whole row takes 17 off every possible assignment, so the best one stays the best. The same goes for columns. Once you can pick a full set of zeros, that assignment costs nothing extra in the reduced matrix, and no entry is negative, so nothing can beat it.

You can reduce the columns first. Every marking guide from 2020 to 2024 accepted either order. The matrices in between differ, the final assignment does not.

Two checkpoints

Worked on a past question

In these tables an orange line through a row or column is a covering line. Shaded cells are covered once, darker cells are covered twice. A black box marks a zero chosen for the assignment. In the worked solutions the covering lines draw themselves in the order you would draw them (most uncovered zeros first), then the chosen zeros are boxed.

Reading the assignment off the zeros

Choosing the zeros is the second judgement point, and it decides the allocation mark. Use the same forced-move routine as a bipartite graph.

1. 1Find a row or column with only one zero. That pairing is forced, so make it.
2. 2Cross out that zero’s row and column. Those can’t be used again.
3. 3Repeat with what is left until every row has a pairing.
4. 4Check: one chosen zero in each row and in each column. Then go back to the original matrix for the values.

Part 4

Too few lines means adjust, then cover again

After both reductions there are not always enough zeros in the right places. The line count tells you. Fewer lines than the size of the matrix means no full set of zeros exists yet, so you adjust and try again.

Finding the fewest lines

1. 1Count the zeros in each row and column.
2. 2Draw a line through the row or column holding the most uncovered zeros.
3. 3Repeat until every zero is covered.
4. 4Check the count a second way: the fewest lines always equals the largest number of zeros you can pick with no two in the same row or column. If you can pick a full set, you are done whatever your lines say.

On a 3 × 3 the greedy count in steps 1 to 3 is nearly always right. On a 4 × 4 or 5 × 5 it can overshoot, and step 4 catches that. Write the count as a statement, the way the 2023 guide does: “2 < 3, so continue algorithm steps” or “3 = 3, so assign tasks”.

The adjustment step

1. 1Find the smallest entry that no line covers. Call it $k$.
2. 2Subtract $k$ from every uncovered entry.
3. 3Add $k$ to every entry covered twice (where a row line crosses a column line).
4. 4Leave entries covered once alone, then cover the zeros again.

This is the same as subtracting $k$ from every uncovered row and adding it back to every covered column, so it never changes which assignment is best. It creates at least one new zero, and because $k$ was the smallest uncovered value, nothing goes negative. Repeat until the lines match the size.

Part 5

When the matrix needs building first, build it, then run the same algorithm

The two biggest assignment questions, 2021 Paper 2 Question 6 (7 marks) and 2024 Paper 2 Question 5 (6 marks), add a layer before or after the algorithm. 2021 gives the distances as expressions in $x$ and the minimum total, and asks for $x$. 2024 gives coordinates, so two distances have to be calculated before the matrix is complete. In both, the algorithm itself is the routine from Parts 3 and 4.

Algebraic entries: run it forwards, solve at the end

1. 1Write the matrix with the algebraic entries.
2. 2Run the reductions, subtracting algebraic minimums exactly as you would numbers. Where every entry in a row (or column) has the same $x$ term, it cancels on that reduction.
3. 3Identify the optimal assignment once the reduced matrix is numeric. Finish the algorithm, including any adjustment, if the lines fall short.
4. 4Write the total of the original entries in those positions, an expression in $x$. Set it equal to the given total and solve.

Entries from coordinates: Earth geometry first

2024 left two entries blank and gave coordinates instead. Two of the six marks were for those distances, so this question tests Topic guide 7, Earth geometry as much as assignment. Points on the same meridian use $D=111.2\times$ angular distance. Points on the same parallel use $D=111.2\cos\theta\times$ angular distance, with $\theta$ the latitude.

Part 6

To maximise, subtract every entry from the largest one first

The algorithm only minimises. When the question wants the largest total (sales, points, profit), convert the matrix first.

1. 1Find the largest value in the whole matrix.
2. 2Subtract every entry from that largest value. This makes a new matrix of “shortfalls”.
3. 3Run the algorithm as normal on the new matrix.
4. 4Read the assignment positions, then take the totals from the original matrix.

The best entries become the smallest shortfalls, so the smallest total shortfall is the largest total. No maximum question has appeared in an external yet, but the 2025 syllabus names it, so it is fair game.

Bigger matrices change nothing in the method. A 5 × 5 needs 5 lines before you assign, and the adjustment may run more than once. The extra risk is arithmetic, so write every matrix out in full.

Worked example: a 4 × 4 maximum

A coach assigns four swimmers to the four legs of a medley relay. The table shows each swimmer’s time-trial points for each stroke, where higher is better. Find the assignment with the largest total.

In step 4, 5 came off the six uncovered entries and went onto Ben’s backstroke and freestyle entries, the two covered twice. Other sets of 3 lines would also cover the zeros in step 3. Any of them works, and leads to the same assignment.

Assign. Cal’s only zero is backstroke and Dee’s only zero is freestyle. With those columns gone, Ana’s remaining zero is breaststroke and Ben takes butterfly. Read the points from the original table:

$$86+70+94+90=340\text{ points}$$

Ana swims breaststroke, Ben butterfly, Cal backstroke and Dee freestyle, for a maximum of 340 points. Ana, who ties for the best backstroke score, does not swim backstroke.

Part 7

Where the marks go, and how not to drop them

The marking guides from 2020 to 2024 give one mark per stage of the algorithm. The pattern barely moves from year to year.

So the reductions alone are worth two marks in every algorithm solution here. A student who reduces correctly and then stalls still banks them.

What the guides and reports reward

• •A separate matrix for each step. The 2022, 2023 and 2024 reports all asked for it. Write each one out in full.
• •Either order. Every guide from 2020 to 2024 accepted the columns reduced before the rows.
• •The line count, stated. 2020 and 2021 named “lines to cover the zeros” as a key step for the communication mark, and 2023 wrote “2 < 3, so continue algorithm steps”. Draw the lines and write the comparison.
• •The assignment in words. Name who does what (“assign Jane to run, Knox to swim and Levi to cycle”) before the arithmetic. It is a mark of its own every time.
• •The total from the original matrix, with units. The reduced values mean nothing in context. 2023’s last mark said “including units”.
• •Follow-through. Every guide from 2020 to 2024 allows follow-through from errors in earlier working. A slip in a reduction does not end the question, so keep going.

Self-checks to run inside the question

Game plan

Your game plan for assignment questions

1. 1Build the matrix: one group as rows, the other as columns. If the question gives a network, coordinates or algebra, fill in every entry first.
2. 2Decide whether you want a minimum or a maximum. For a maximum, subtract every entry from the largest entry and work on the new matrix.
3. 3Reduce each row by its smallest value, then each column by its smallest value (either order). Write a new matrix each time and check for a zero in every row and column.
4. 4Cover all the zeros with the fewest lines and write the count against the size: “2 < 3, so continue” or “3 = 3, so assign”.
5. 5If there are too few lines, subtract the smallest uncovered value from every uncovered entry, add it to every entry covered twice, and cover again.
6. 6Pick one zero in each row and column, starting from any row or column with only one zero, and state the assignment in words.
7. 7Add the original values, not the reduced ones, and answer in context with units. If a value was unknown, set the total equal to the given total and solve.