The Assignment Problem

Who should do which job?

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Assign n workers to n jobs to minimise total cost: n! possibilities.
• Greedy choices can fail; the Hungarian method finds the optimum in about n³ steps.
• Adding a constant to a row or column doesn’t change the best assignment.

Steps

1. Pairing people with jobs
2. Too many to check
3. Find the cheapest assignment
4. Grab the best first?
5. Shifting a row
6. Brute force for twenty