Hungarian Assignment Algorithm
A Hungarian Assignment Algorithm is an assignment algorithm that is a combinatorial optimization algorithm.
- AKA: Kuhn-Munkres Algorithm.
- Context:
- It can be applied by a Hungarian Assignment-based System (to solve a linear assignment task).
- See: Combinatorial Optimization, Polynomial Time, Primal-Dual Method, Assignment Task.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Hungarian_algorithm Retrieved:2014-8-22.
- The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.[1] [2]
James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.[3] Since then the algorithm has been known also as Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was [math]\displaystyle{ O(n^4) }[/math], however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an [math]\displaystyle{ O(n^3) }[/math] running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin. [4]
- The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.[1] [2]
- ↑ Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2:83–97, 1955. Kuhn's original publication.
- ↑ Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.
- ↑ J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
- ↑ http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Assignment_problem#Algorithms_and_generalizations Retrieved:2014-8-22.
- 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.
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. If the cost function involves quadratic inequalities it is called the quadratic assignment problem.
- 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.
1955
- (Kuhn, 1955) ⇒ Harold W. Kuhn. (1955). “The Hungarian method for the assignment problem." Naval research logistics quarterly, 2(1-2).