Course contentsShow
← Computer Science
Lesson 1049 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Assignment Problem

Solve the assignment problem using min-cost max flow to assign agents to tasks optimally.

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:

  1. Create a flow network: source → agents → tasks → sink
  2. Capacities: Every edge has capacity 1 (ensuring one-to-one assignments)
  3. Costs: Each agent→task edge has cost equal to the assignment cost; all other edges have cost 0
  4. 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.