Assignment problem

The assignment problem is a fundamental challenge in combinatorial optimization. It involves matching a set of agents to a set of tasks. Each possible pairing between an agent and a task has a specific cost. This cost might represent time, money, or distance. The goal is to assign at most one agent to each task and at most one task to each agent. We want to do this while making the total cost of all assignments as low as possible. This problem is essential for organizing complex systems efficiently.

To understand how it works, imagine a taxi company with three drivers and three customers. The cost for a driver to reach a customer depends on the travel time. This is a balanced assignment because the number of agents equals the number of tasks. In graph theory, this is described using a weighted bipartite graph. We look for a matching of maximum size where the sum of the edge weights is minimized. If the costs are added up for every single agent and task, it is called a linear assignment problem. The term "linear" refers to the fact that the cost function and constraints use only linear terms.

There are different types of assignment problems based on how the groups are sized. A balanced assignment occurs when both sets have the same number of vertices, denoted as n. An unbalanced assignment happens when one set is larger than the other. For example, you might have four taxis but only three customers. You can solve this by inventing a "dummy" task. This dummy task has a cost of zero for the extra taxi. This trick turns an unbalanced problem into a balanced one. You can also adapt the rules to maximize profit instead of minimizing cost.

Solving these puzzles requires smart mathematical strategies. A naive approach is to check every possible assignment. However, with n agents and n tasks, there are n! (n factorial) different assignments. This becomes too slow very quickly. Another way is the greedy algorithm. This method picks the cheapest available pair first and removes them from the list. While simple, the greedy method often fails to find the best total cost. For example, choosing a very cheap match for Alice might force George into a very expensive match. A better total solution might exist if Alice took a slightly more expensive task.

Mathematicians have developed much more efficient algorithms to find the optimal solution. One of the first polynomial-time algorithms for balanced assignment is the Hungarian algorithm. It is a global algorithm that improves matchings along augmenting paths. These are alternating paths between unmatched vertices. The Hungarian algorithm is very fast and can even use parallel computing or GPU acceleration. Other approaches are local methods, such as auction algorithms or preflow-push algorithms. These focus on finding small, local updates rather than looking at the entire graph at once.

Another powerful way to solve the problem is through linear programming. You can represent the assignment as a mathematical model with variables. Each variable is 1 if an edge is used and 0 if it is not. You add constraints to ensure every vertex is connected to exactly one edge. Even though this is an integer linear program, it can be solved as a continuous program. This works because the constraint matrix is totally unimodular. This mathematical property ensures the solution will naturally result in whole numbers.

Finally, the assignment problem connects to many broader mathematical fields. It is a special case of the transportation problem. It is also a specific type of the minimum cost flow problem. You can even expand the rules for many-to-many assignments. In this version, an agent has a capacity to handle multiple tasks. For example, one taxi might carry a group of several customers. This can be solved by building a flow network with layers for sources, agents, tasks, and sinks.