Assignment Problems

Who does 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

• Assignment problems match workers to jobs at minimum total cost.
• Brute force grows like n!, but the Hungarian method is fast.
• Special structure can make whole-number problems easy.

Steps

1. Matching workers to jobs
2. Find the best assignment
3. How many assignments?
4. The Hungarian method
5. Polynomial time
6. Easy despite whole numbers