Polynomial-time algorithm for the assignment problem
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 in 1955 by Harold Kuhn, who gave it 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] However, 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.[3]
James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.[4] Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was , however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an running time.[5][6] Ford and Fulkerson extended the method to general maximum flow problems in form of the Ford–Fulkerson algorithm.
^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.
^"Presentation". Archived from the original on 16 October 2015.
^J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
^Edmonds, Jack; Karp, Richard M. (1 April 1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems". Journal of the ACM. 19 (2): 248–264. doi:10.1145/321694.321699. S2CID 6375478.
^Tomizawa, N. (1971). "On some techniques useful for solution of transportation network problems". Networks. 1 (2): 173–194. doi:10.1002/net.3230010206. ISSN 1097-0037.
and 22 Related for: Hungarian algorithm information
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual...
Hungarians/Magyars, ethnic groups in HungaryHungarianalgorithm, a polynomial time algorithm for solving the assignment problem Hungarian language, a Finno-Ugric...
Coloring algorithm: Graph coloring algorithm. Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching Hungarianalgorithm: algorithm...
One of the first polynomial-time algorithms for balanced assignment was the Hungarianalgorithm. It is a global algorithm – it is based on improving a matching...
Although with the auction algorithm the total benefit is monotonically increasing with each iteration, in the Hungarianalgorithm (from Kuhn, 1955; Munkres...
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order...
possible pairings of an example to a class, and then employ the Hungarianalgorithm to maximize the sum of the c selected scores over all c! possible...
elements. This is a linear assignment problem, and can be solved by the Hungarianalgorithm in cubic time. Let μ 1 = N ( m 1 , C 1 ) {\displaystyle \mu _{1}={\mathcal...
bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates-Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells...
system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write...
component of the underlying undirected graph. Fleury's algorithm is an elegant but inefficient algorithm that dates to 1883. Consider a graph known to have...
algorithm, or stemmer. A stemmer for English operating on the stem cat should identify such strings as cats, catlike, and catty. A stemming algorithm...
The Hungarian alphabet (Hungarian: magyar ábécé) is an extension of the Latin alphabet used for writing the Hungarian language. The alphabet is based...
Hungarian Americans (Hungarian: Amerikai magyarok) are Americans of Hungarian descent. The U.S. Census Bureau has estimated that there are approximately...
half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary...
'logical' one. Thus, in order to offer bidi support, Unicode prescribes an algorithm for how to convert the logical sequence of characters into the correct...
is known as the assignment problem, and it can be solved by the Hungarianalgorithm in time O ( n 3 ) {\displaystyle O(n^{3})} (where n {\displaystyle...
station code Kent M. Pitman, known as KMP Knuth–Morris–Pratt algorithm, a search algorithm K-Multimedia Player KM Produce, a Japanese adult video company...
Global Information
