Assignment problem
Contents
1 Formulation of the problem
Suppose that there are [math]n[/math] agents and [math]m[/math] tasks, which can be distributed between these agents. Only one task can be assigned to each agent, and each task can be assigned to only one agent. The cost of assignment of the [math]i[/math]-th task to the [math]j[/math]-th agent is [math]c(i, j)[/math]. If [math]c(i, j) = \infty[/math], then the [math]i[/math]-th task cannot be assigned to the [math]j[/math]-th agent.
The assignment problem: find a feasible set of assignments [math]A = \{ (i_1, j_1), \ldots, (i_k, j_k) \}[/math], [math]k = \min \{m, n\}[/math] having the maximum total cost:
- [math] C(A) = \sum_{s = 1}^k c(i_s, j_s) \to \max. [/math]
2 Variants of the problem
If [math]m = n[/math], then we say of the linear assignment problem: each agent is assigned to perform exactly one task, and each task is assigned to exactly one agent.
In the case of unit weights, we have to find a maximum matching in a bipartite graph, and the problem reduces to assigning as much tasks as possible.
3 Algorithms for solving the problem
- The Hungarian Method[1][2][3] for the linear problem. The complexity is [math]O(n^4)[/math] (and can be reduced [4] to [math]O(n^3)[/math]);
- the auction algorithm[5][6];
- the Hopcroft-Karp algorithm[7] for the problem with unit weights. The complexity is [math]O(m \sqrt{n})[/math].
4 References
- ↑ Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.
- ↑ Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.
- ↑ Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.
- ↑ Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.
- ↑ Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.
- ↑ Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.
- ↑ Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.
