QCE General Mathematics - Unit 4 - Networks and decision mathematics 2

Assigning Order and the Hungarian Algorithm | QCE General Mathematics

Learn allocation problems, bipartite graphs, inspection and the Hungarian algorithm for QCE General Mathematics.

Updated 2026-05-18 - 5 min read

Assignment problems match items from one group to items from another group. A school might assign teachers to classes, workers to tasks, or delivery drivers to routes. The aim is usually to minimise cost or time, or maximise score.

Representing assignments

Assignment problems can be represented as:

• a bipartite graph
• a table of costs or benefits
• a matrix

Small problems may be solved by inspection. Larger $3\times3$ to $5\times5$ square matrices can use the Hungarian algorithm.

Hungarian algorithm outline

For a minimisation problem:

1. Subtract the smallest entry in each row from every entry in that row.
2. Subtract the smallest entry in each column from every entry in that column.
3. Cover all zeroes with the minimum number of horizontal and vertical lines.
4. If the number of lines equals the matrix order, make an assignment using independent zeroes.
5. If not, adjust the uncovered entries and repeat.

Worked example

Maximum problems

For maximisation, convert the table to an equivalent minimisation problem by subtracting each entry from the largest entry in the table. Then apply the algorithm.

Solving by inspection

For small allocation tables, inspection may be faster than the full algorithm. Look for a row or column with one clearly best option, assign it, then remove that row and column from consideration. Check that the final assignment uses every row and column once.

Detailed Hungarian adjustment step

After row and column reduction, cover all zeroes with the fewest horizontal and vertical lines.

If the number of covering lines is less than the matrix order:

1. Find the smallest uncovered number.
2. Subtract it from every uncovered entry.
3. Add it to every entry at an intersection of two covering lines.
4. Leave all other entries unchanged.
5. Cover zeroes again and test for an assignment.

This creates more zeroes while preserving the relative costs of assignments.

Choosing independent zeroes

An independent zero is a zero whose row and column are not already used. Start with any row or column that has only one available zero. Continue until each row and column has exactly one assignment.

Maximum assignment problems

For a maximisation problem, first convert scores to costs:

$ \text{cost}=\text{largest score}-\text{score} $

Then apply the minimisation algorithm. Convert the final assignment back to the original scores when reporting the result.

Depth: full minimisation example

Consider this cost table.

| Worker | Task A | Task B | Task C | |---|---:|---:|---:| | W1 | 12 | 9 | 15 | | W2 | 10 | 11 | 8 | | W3 | 14 | 7 | 13 |

First subtract the smallest value in each row:

| Worker | Task A | Task B | Task C | |---|---:|---:|---:| | W1 | 3 | 0 | 6 | | W2 | 2 | 3 | 0 | | W3 | 7 | 0 | 6 |

Then subtract the smallest value in each column. Column A has minimum $2$, column B has minimum $0$, and column C has minimum $0$.

| Worker | Task A | Task B | Task C | |---|---:|---:|---:| | W1 | 1 | 0 | 6 | | W2 | 0 | 3 | 0 | | W3 | 5 | 0 | 6 |

Independent zeroes can be chosen as W1-B, W2-A and W3 has no remaining independent zero in C, so this set fails. Try W1-B, W2-C and W3-A is not zero. There are not enough independent zeroes yet, so the cover-and-adjust step may be required.

This example shows why the algorithm is more than simply "pick zeroes". The independent-zero condition is essential.

Rectangular tables

Some assignment tables are not square. The Hungarian algorithm requires a square matrix, so add dummy rows or columns with zero cost where needed. A dummy assignment means one worker or task is unused. In final answers, do not report a dummy as a real task.

Maximisation by conversion

For a score table, convert to costs using:

$ \text{cost}=\text{largest score}-\text{score} $

This preserves the best assignment because high scores become low costs.

Reporting allocation answers

A complete answer lists:

• each row item and its assigned column item
• the original cost or score for each assignment
• the minimum total cost or maximum total score
• any dummy assignment if a rectangular table was used

Depth: tie handling

Assignment problems can have ties. A tie does not mean the algorithm has failed. It may mean there is more than one optimal assignment.

When independent zeroes can be selected in multiple ways, test each possible complete assignment if needed and compare the original totals. If two assignments have the same minimum cost or maximum score, both are valid.

For written solutions, show enough working that the selected assignment is clearly valid: each row used once, each column used once, and the total calculated from the original table.

Quick check

Sources

• QCAA General Mathematics subject page
• QCAA General Mathematics 2025 syllabus
• QCAA General Mathematics 2025 formula book
• Lumen Learning: The Hungarian Method