7.5 The assignment problem

Assigning \(n\) workers to \(n\) jobs, one each, with cost \(c_{ij}\) for worker \(i\) on job \(j\), is the transportation problem with all \(s_i = d_j = 1\): \[ \text {minimise } \sum _{i,j}c_{ij}x_{ij} \quad \text {subject to}\quad \sum _jx_{ij} = 1, \quad \sum _ix_{ij} = 1, \quad x_{ij} \geq 0 . \] By total unimodularity its vertices are \(0\)–\(1\) matrices with one \(1\) in each row and column, permutation matrices; this is the Birkhoff–von Neumann theorem, that the doubly stochastic matrices are the convex hull of the permutation matrices. The LP solves the combinatorial problem, but every BFS has \(2n - 1\) basic cells of which only \(n\) are positive: the assignment problem is highly degenerate, and the simplex method crawls on it. The Hungarian method of Kuhn (1955), based on theorems of König and Egerváry, works directly with the costs.

(1): Subtract the smallest entry of each row from that row, then the smallest entry of each column from that column. This changes every assignment’s cost by the same constant, so the optimal assignments are unchanged, and leaves a non-negative matrix with a zero in every row and column.
(2): Cover all the zeros with the fewest possible horizontal and vertical lines. By König’s theorem, the fewest lines equals the largest number of zeros no two in the same row or column. If it is \(n\), those \(n\) independent zeros give an assignment of reduced cost \(0\), which is optimal since all reduced costs are non-negative.
(3): Otherwise, let \(\delta \) be the smallest uncovered entry; subtract it from every uncovered entry and add it to every entry covered twice. This is again the subtraction of constants from rows and the addition to columns, it keeps the matrix non-negative, and it creates a new zero. Return to (2).

Example 7.5.1. For the cost matrix with rows \((9, 11, 14, 11)\), \((6, 15, 13, 13)\), \((12, 13, 6, 8)\), \((11, 9, 10, 9)\), subtracting the row minima \(9, 6, 6, 9\) gives rows \((0, 2, 5, 2)\), \((0, 9, 7, 7)\), \((6, 7, 0, 2)\), \((2, 0, 1, 0)\), whose column minima are all \(0\). The zeros can be covered by three lines (column \(1\), rows \(3\) and \(4\)), so only three independent zeros exist: workers \(1\) and \(2\) both have their only zero in column \(1\). The smallest uncovered entry is \(\delta = 2\); the step gives rows \((0, 0, 3, 0)\), \((0, 7, 5, 5)\), \((8, 7, 0, 2)\), \((4, 0, 1, 0)\), which have four independent zeros, for example \((1, 2)\), \((2, 1)\), \((3, 3)\), \((4, 4)\). The optimal cost is \(11 + 6 + 6 + 9 = 32\); the assignment \((1, 4)\), \((2, 1)\), \((3, 3)\), \((4, 2)\) is equally good.

A maximisation problem is converted by subtracting every entry from the largest; impossible assignments get a very large cost; and a rectangular problem is made square with dummy rows or columns of zeros. The Hungarian method runs in \(O(n^3)\) time.

[next] [prev] [prev-tail] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.