Assignment problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching (or minimum weight perfect matching) in a weighted bipartite graph.
In its most general form, the problem is as follows:
If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the linear assignment problem. Commonly, when speaking of the assignment problem without any additional qualification, then the linear assignment problem is meant.
The Hungarian algorithm is one of many algorithms that have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents. Other algorithms include adaptations of the primal simplex algorithm, and the auction algorithm.
The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure.
When a number of agents and tasks is very large, a parallel algorithm with randomization can be applied. The problem of finding minimum weight maximum matching can be converted to finding a minimum weight perfect matching. A bipartite graph can be extended to a complete bipartite graph by adding artificial edges with large weights. These weights should exceed the weights of all existing matchings to prevent appearance of artificial edges in the possible solution. As shown by Mulmuley, Vazirani & Vazirani (1987), the problem of minimum weight perfect matching is converted to finding minors in the adjacency matrix of a graph. Using the isolation lemma, a minimum weight perfect matching in a graph can be found with probability at least ½. For a graph with n vertices, it requires time.
...
Wikipedia