Assignment Problem (Hungarian Method)
Match agents to tasks in the best possible way. The assignment problem finds the one-to-one pairing of workers to jobs, machines to tasks, that minimizes total cost or maximizes total value, solved efficiently by the Hungarian method.
Solve Assignment Problem →What is the Assignment Problem?
The assignment problem is the task of assigning a set of agents to a set of tasks on a one-to-one basis so as to minimize total cost (or maximize total value). Each agent is assigned to exactly one task and each task to exactly one agent, with a known cost for every possible agent-task pairing.
It is a special case of the transportation problem in which each source (agent) has a supply of one and each destination (task) has a demand of one. This structure gives it a particularly clean form, and although it could be solved as a general linear or integer program, its special structure allows a much faster dedicated algorithm.
That algorithm is the Hungarian method, an efficient combinatorial procedure that solves the assignment problem in polynomial time. Because assignment problems arise constantly, matching workers to jobs, machines to orders, or players to positions, the Hungarian method is one of the most useful classical algorithms in operations research.
In plain terms: You have, say, four workers and four jobs, and each worker costs a different amount to do each job. The assignment problem finds the pairing, one worker per job, that costs the least in total. The Hungarian method solves it fast, without trying every combination.
Key Points
One-to-One Matching
Each agent gets exactly one task and each task exactly one agent, with a cost for every pairing.
Special Transportation Case
Every source has supply one and every destination demand one, giving a clean structure solvable efficiently.
Hungarian Method
A dedicated polynomial-time algorithm that solves the assignment problem far faster than a general LP or brute force.
Key Formulas
Understanding the Solution
The solution is a complete one-to-one matching and its total cost, the minimum achievable. The Hungarian method guarantees this optimum, unlike a greedy approach that pairs each agent with its individually cheapest task, which can be far from optimal because of the one-to-one constraint.
The same method handles maximization (assigning to maximize value or profit) by converting it to an equivalent minimization, and it accommodates unbalanced problems, where agents and tasks differ in number, by adding dummy rows or columns. This flexibility makes it broadly applicable.
Assumptions & Validation
One-to-One Structure
Each agent takes one task and each task one agent.
If violated: For many-to-one assignments, use a transportation or general LP formulation.
Known Costs
The cost (or value) of every agent-task pairing is known.
If violated: Estimate all pairing costs; missing entries need handling.
Balanced or Dummied
Agents and tasks are equal in number, or balanced with dummies.
If violated: Add dummy rows or columns for unbalanced problems.
⚠️ Check assumptions first
A tempting but wrong approach is to assign each agent to its individually cheapest task greedily; the one-to-one constraint means this often gives a poor total, and the Hungarian method exists precisely to find the true optimum. The problem must be balanced (equal agents and tasks) or balanced with dummy rows or columns, and every pairing cost must be known. For many-to-one matching, the assignment structure does not apply.
When NOT to Use Assignment Problem
Many-to-One Matching
When one agent can take several tasks, use a transportation or general integer-programming formulation.
Routing Between Stops
To sequence visits to many locations, use the traveling salesman or vehicle routing problem.
Capacitated Flow
For flow through a network with capacities, use network-flow models.
Industry Applications
Workforce Scheduling
Assign workers to jobs or shifts to minimize cost or maximize suitability.
Machine-Task Allocation
Match machines to orders to minimize processing time or cost.
Resource Matching
Pair resources to demands one-to-one at least cost.
Sports & Scheduling
Assign players to positions or referees to games optimally.
Frequently Asked Questions
What is the assignment problem?
The assignment problem is the task of pairing a set of agents with a set of tasks on a one-to-one basis to minimize total cost or maximize total value. Each agent is assigned exactly one task and each task exactly one agent, given a known cost for every possible pairing. It arises whenever resources must be matched to demands one-to-one, such as workers to jobs or machines to orders.
What is the Hungarian method?
The Hungarian method is an efficient combinatorial algorithm that solves the assignment problem to optimality in polynomial time. It systematically manipulates the cost matrix to find the minimum-cost one-to-one assignment without enumerating all possibilities. Because assignment problems are so common, the Hungarian method is one of the most widely used classical algorithms in operations research.
How is the assignment problem related to the transportation problem?
The assignment problem is a special case of the transportation problem in which every source has a supply of exactly one and every destination has a demand of exactly one. This structure means it could be solved as a transportation or linear program, but its special form allows the faster dedicated Hungarian method. The connection places the assignment problem within the broader family of network optimization problems.
Why not just assign each agent to its cheapest task?
Assigning each agent greedily to its individually cheapest task ignores the one-to-one constraint and usually gives a poor total. Two agents might both be cheapest on the same task, and resolving such conflicts myopically leads far from the optimum. The Hungarian method accounts for all interactions between assignments, guaranteeing the minimum total cost that a greedy approach cannot ensure.
Can the assignment problem handle maximization?
Yes. Although it is usually stated as cost minimization, the assignment problem readily handles maximization of value or profit by converting the maximization into an equivalent minimization, for example by subtracting each value from a large constant. The Hungarian method then solves the transformed problem, and the resulting assignment maximizes total value. This makes the method applicable to both cost and benefit objectives.
What if the numbers of agents and tasks differ?
When agents and tasks are unequal in number, the problem is unbalanced and is handled by adding dummy agents or dummy tasks with zero cost to make the numbers equal. The dummy entries absorb the surplus without affecting the real assignments' cost. After balancing, the Hungarian method solves the problem normally, and the dummy assignments are simply ignored in the final result.
Match Agents to Tasks Optimally
Solve the assignment problem with the Hungarian method. Free during Beta.
Solve Assignment Problem →