Assignment Problem
You'll learn how to assign agents to tasks optimally using the minimum-cost maximum-flow approach you've already mastered.
What Is the Assignment Problem?
The assignment problem asks: given n agents and n tasks, with each agent–task pair having a specific cost, how do you assign each agent to exactly one task (one-to-one) so that the total cost is minimized?
Think of it like assigning workers to jobs, students to projects, or delivery drivers to routes—where everyone gets exactly one assignment and you want the cheapest overall solution.
Modeling as Min-Cost Max Flow
You already know bipartite matching finds if a perfect matching exists. The assignment problem goes further: among all perfect matchings, find the cheapest one.
Here's how to model it as a min-cost max-flow problem:
- Create a flow network: source → agents → tasks → sink
- Capacities: Every edge has capacity 1 (ensuring one-to-one assignments)
- Costs: Each agent→task edge has cost equal to the assignment cost; all other edges have cost 0
- Flow requirement: Push flow of n from source to sink
When you solve for minimum-cost maximum-flow with flow value n, you get a perfect matching where the total flow cost equals the minimum assignment cost. Each unit of flow from agent i to task j means "assign agent i to task j."
Why It Works
Maximum flow ensures everyone gets assigned (flow = n). The min-cost part ensures you choose the cheapest set of assignments among all valid perfect matchings. The capacity-1 constraint prevents double assignments.
Key Takeaway: The assignment problem finds the minimum-cost perfect matching by modeling it as a min-cost max-flow problem with unit capacities and assignment costs on bipartite edges.