Assignment problem (Hungarian method)

At a Glance

• Frequency: 6 sub-parts across 6 of 13 years (2013, 2015, 2018, 2021, 2023, 2024)
• Priority tier: T2
• Marks (count): 10 (2), 15 (2), 20 (2)
• Average solve time: ~18 min
• Difficulty mix: hard 3, medium 3
• Section: A | Dominant type: computation

Why This Chapter Matters

Assignment problems appear in 6 of the last 13 years at 10–20 marks in Section A. The standard variant is the Hungarian method for minimising total cost; two harder variants appear: forbidden cells (assign $\infty$ cost and re-run), and the 2013 bottleneck problem (minimise the maximum cost in the assignment). The Hungarian algorithm is longer than it looks — typically 3–5 matrix revisions — and requires careful bookkeeping. The two 20-mark questions (2023, 2024) test the full algorithm including additional constraints, so full procedural fluency is essential.

Minimum Theory

Assignment problem. Assign $n$ agents to $n$ tasks one-to-one to minimise the total cost $\sum c_{i\sigma(i)}$. An $m\times n$ matrix with $m<n$: add $n-m$ dummy rows with all zeros. If maximising, convert to minimisation by subtracting all entries from the maximum entry.

Hungarian algorithm (minimisation).

1. Row reduction: subtract each row’s minimum from that row.
2. Column reduction: subtract each column’s minimum from the resulting matrix.
3. Cover all zeros with the minimum number of lines $\ell$. If $\ell=n$, proceed to step 5.
4. Revise the matrix: find the smallest uncovered element $\delta$. Subtract $\delta$ from every uncovered element; add $\delta$ to every doubly-covered element; singly-covered elements unchanged. Go to step 3.
5. Find an optimal assignment from the zeros: look for a zero in a row (or column) that has only one zero; assign it; cross out that row and column; repeat for the remaining rows/columns. If multiple zeros in some rows, use trial-and-error.
6. Report cost using the original matrix (not the reduced one).

Forbidden cells. Set $c_{ij}=\infty$ (a very large number, e.g. $M$) for any forbidden assignment. The algorithm will not select that cell.

Bottleneck assignment. Minimise $\max_{i} c_{i\sigma(i)}$ rather than $\sum c_{i\sigma(i)}$. Algorithm: find the smallest threshold $T$ such that the bipartite graph with edges $\{(i,j):c_{ij}\le T\}$ has a perfect matching. Try thresholds in increasing order of the cost values.

Question Archetypes

Two patterns cover every assignment question in the corpus.

hungarian-assignment (5 question(s); 2015, 2018, 2021, 2023, 2024)

Recognition Cues

• “Find the optimal assignment to minimise/maximise total [cost/time].”
• “Assignment is not possible for [person $i$, task $j$]” — forbidden cell; set to $M$ or $\infty$.
• An $m\times n$ matrix with $m\ne n$ — add dummy row(s) or column(s) of zeros.

Solution Template

1. Balance (if needed): add dummy rows/columns of zeros.
2. Convert to minimisation if asked to maximise: subtract all from the largest entry.
3. Row-reduce, then column-reduce.
4. Cover zeros with minimum lines; if $<n$, revise as described above; repeat.
5. Assign: scan for singleton zeros; cross out row and column; continue.
6. State cost from the original matrix.

Worked Example(s)

2024 Paper 2, 2024-P2-Q4c (20 marks)

3 officers (A, B, C) to 4 offices (Delhi, Mumbai, Kolkata, Chennai); minimise relocation cost.

Add dummy officer D with all zeros (making a 4×4 matrix).

Row reduction: rows A (min 16), B (min 10), C (min 10), D (min 0): $\begin{pmatrix}0&6&8&4\\0&22&16&6\\0&10&36&20\\0&0&0&0\end{pmatrix}.$

Column reduction: all column minima = 0; no change.

Cover zeros (minimum lines): column 1 + row D = 2 lines $<4$.

Revise ($\delta=4$): uncovered cells (rows A,B,C × cols 2,3,4) subtract 4; doubly-covered cell (D,col 1) adds 4: $\begin{pmatrix}0&2&4&0\\0&18&12&2\\0&6&32&16\\4&0&0&2\end{pmatrix}.$

Cover again: col 1, row A, row D = 3 lines $<4$.

Revise ($\delta=2$): uncovered = rows B,C × cols 2,3,4: $\begin{pmatrix}2&0&2&0\\0&14&8&0\\0&2&28&14\\6&0&0&2\end{pmatrix}.$

Cover again: row A, row D, col 1, col 4 = 4 lines = $n$. Optimal.

Assign zeros: Row C: only zero at col 1 (Delhi) → C→Delhi. Row B: zeros at col 1 (taken), col 4 → B→Chennai. Row A: zeros at col 2, col 4 (taken) → A→Mumbai. Row D: zeros at col 2 (taken), col 3 → D→Kolkata (dummy, unfilled).

$\boxed{A\to\text{Mumbai (22)},\;B\to\text{Chennai (16)},\;C\to\text{Delhi (10)};\;\text{total}=\text{₹48{,}000}.}$

2023 Paper 2, 2023-P2-Q4c (20 marks)

5×5 assignment; minimise total time; also find optimum if subordinate IV cannot do job C.

Unrestricted optimum (standard Hungarian): assignment I→E, II→D, III→B, IV→C, V→A; total 33 hours.

For the restricted variant (IV≠C): set $c_{\text{IV,C}}=\infty$ and re-run. The algorithm proceeds identically until the revision step, where a different uncovered minimum is chosen; the restricted optimal is 34 hours.

Common Traps

• Forbidden cells: assign a large $M$ to the cost, then proceed normally. If the algorithm returns an assignment using that cell, something went wrong in the coverage/revision steps.
• Maximisation conversion: subtract each element from the matrix maximum (not from each row maximum). A single global maximum ensures the resulting matrix is non-negative everywhere.
• Singleton-zero search: when all remaining rows have two or more zeros, try one assignment and check whether it blocks another row; if so, backtrack and try the other zero. This “trial” step is necessary and is not always smooth.
• Dummy rows/columns: in an $m<n$ problem, the dummy agent gets the “least desirable” assignment (whichever column/row goes to the dummy is left unassigned). Don’t count the dummy’s cost.

bottleneck-assignment (1 question(s); 2013)

Recognition Cues

• “Minimum time assignment problem” — the goal is to minimise the longest individual task time.
• Distinct from standard assignment: total cost is not summed; only the maximum matters.

Solution Template

1. List all distinct cost values in ascending order.
2. For each threshold $T$ (starting from the smallest that could possibly give a perfect matching), check whether the bipartite graph with edges $\{(i,j):c_{ij}\le T\}$ has a perfect matching.
3. The smallest such $T$ is the optimal bottleneck value. State the assignment achieving it.

Worked Example(s)

2013 Paper 2, 2013-P2-Q4a (15 marks)

$4\times4$ bottleneck assignment: minimise the maximum individual time.

Cost matrix: $J_1[3,12,5,14]$, $J_2[7,9,8,12]$, $J_3[5,11,10,12]$, $J_4[6,14,4,11]$.

At $T=10$: no row has access to $M_4$ (cheapest for $M_4$ is 11) — no perfect matching.

At $T=11$: $J_4$ can use $M_4$ (cost 11); remaining $J_1\to M_1(3)$, $J_2\to M_2(9)$, $J_3\to M_3(10)$ — all $\le11$. Perfect matching exists.

$\boxed{J_1\to M_1,\;J_2\to M_2,\;J_3\to M_3,\;J_4\to M_4;\;\text{maximum time}=11.}$

Common Traps

• This is not the same as minimising the sum — do not apply the standard Hungarian algorithm.
• At each threshold, explicitly check whether Hall’s condition (or a direct greedy matching) is satisfied. A perfect matching exists iff every row has at least one allowed column AND the graph has no “bottleneck” subset with too few available columns.

Practice Set

• 2015-P2-Q1e (10 m) — — 5×5 assignment, maximisation (convert first); straightforward.
• 2018-P2-Q4c (15 m) — — 5×5 with two forbidden cells; tests $M$-substitution.