Assignment problem with a certificate: LP duality, potentials and the Hungarian method

A tutoring service sends each of its four tutors to a different one of its four students. Tutor $i$ needs $c_{i j}$ minutes to reach student $j$ , as in the figure. An assignment pairs every tutor with a different student and costs the total travel time. The service wants the cheapest assignment, and it wants to prove to its tutors that no cheaper one exists, without listing all $n!$ assignments.

Minutes from each tutor (row) to each student (column).

The proof is a set of potentials: a number $u_{i}$ for each tutor and $v_{j}$ for each student, with $u_{i} + v_{j} \leq c_{i j} for every tutor i and student j .$ Any assignment pairs each tutor with one student, so it costs at least $\sum_{i} u_{i} + \sum_{j} v_{j}$ . If an assignment costs exactly that much, it is optimal, and the potentials are its certificate.

Background: LP Duality.

Part A: 9 minutes

Tutor 0 goes to student 3 (1 minute), tutor 1 to student 1 (4), tutor 2 to student 0 (2) and tutor 3 to student 2 (2): 9 minutes. Every other rota takes at least 13. Sending each tutor in turn to their nearest free student starts with $1 + 1 + 2$ and then has to send tutor 3 to student 1, which takes 9 minutes, so it costs 13. Taking the cheapest remaining pair each time does the same.

Part B: a certificate

The potentials $u = (2, 4, 2, 5), v = (0, 0, - 3, - 1)$ satisfy $u_{i} + v_{j} \leq c_{i j}$ for all 16 pairs, and add up to $13 - 4 = 9$ . So no rota is shorter than 9 minutes, and the rota from part A is optimal. Certificates are not unique. Adding the same number to every $u_{i}$ and subtracting it from every $v_{j}$ gives another, and other choices work too.

Why the bound holds: an assignment uses each tutor once and each student once, so its cost is $\sum_{i} c_{i, m (i)} \geq \sum_{i} (u_{i} + v_{m (i)}) = \sum_{i} u_{i} + \sum_{j} v_{j} .$ Equality needs $u_{i} + v_{m (i)} = c_{i, m (i)}$ on every matched pair. This is complementary slackness: the assignment may use only pairs whose constraint is tight.

Part C: the Hungarian method

The assignment problem is a linear program: choose $x_{i j} \geq 0$ with every row and column summing to 1, minimising $\sum c_{i j} x_{i j}$ . Its dual is exactly the problem of part B: maximise $\sum u_{i} + \sum v_{j}$ subject to $u_{i} + v_{j} \leq c_{i j}$ . The Hungarian method works on both at once:

Keep feasible potentials. Call a pair tight when $u_{i} + v_{j} = c_{i j}$ .
Grow a matching using tight pairs only. To add tutor $i$ , search from $i$ for an alternating path, through tight pairs, that ends at a free student.
If the search gets stuck, let $δ$ be the smallest reduced cost $c_{i j} - u_{i} - v_{j}$ from a reached tutor to an unreached student. Raise the reached tutors' $u$ by $δ$ and lower the reached students' $v$ by $δ$ . Feasibility survives, matched pairs stay tight, and at least one new pair becomes tight.

Each tutor is added after at most $n$ adjustments of $O (n)$ work each, with the $min$ values kept up to date, so the method runs in $O (n^{3})$ . When every tutor is matched, all matched pairs are tight, so the potentials add up to the cost. That is the certificate the grader checks.

The same algorithm is successive shortest paths in a minimum-cost flow network, with $u$ and $v$ as the node potentials that keep reduced costs non-negative. Any method that returns a valid certificate passes.

Three near-misses fail the grader:

Right rota, weak potentials. Each tutor's cheapest trip as $u_{i}$ , with $v = 0$ , is feasible, but on the statement's rota it proves only 6.
Right sum, infeasible potentials. Charging each tutor exactly their own trip makes the sum match the cost. But tutor 1 has a 1-minute trip, so $u_{1} + v_{2} = 4 > 1$ .
The cheapest remaining pair, again and again, gives a 13-minute rota. Reducing rows and then columns gives potentials worth 9 here, the true optimum, so the grader reports that this rota is the one that is wrong.

Going further

Prices and auctions. Read $- v_{j}$ as student $j$ 's price and $u_{i}$ as tutor $i$ 's profit at those prices. Bertsekas's auction algorithm has tutors bid for their best student, raising the price by the gap to their second best plus $ε$ . It ends with a rota within $n ε$ of optimal, which is exact for whole-number costs when $ε < 1 / n$ .
Whole numbers. The constraint matrix of the assignment LP is totally unimodular, so with whole-number costs both the LP and its dual have whole-number optimal solutions. That is why the potentials above are whole numbers. See Polytopes and Integrality.
Certificates in general. An optimisation answer that comes with a dual certificate can be checked in far less time than it took to find, here $O (n^{2})$ against $O (n^{3})$ .

References

H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 1955.
J. Munkres. Algorithms for the assignment and transportation problems. Journal of the SIAM 5(1), 1957.
J. Edmonds, R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2), 1972.
D. P. Bertsekas. The auction algorithm: a distributed relaxation method for the assignment problem. Annals of Operations Research 14, 1988.

The Tutoring Rota

Try your rule first

Part A: 9 minutes

Part B: a certificate

Part C: the Hungarian method

Going further

References

The shortest rota