Lesson plan

Hungarian algorithm

The Hungarian algorithm or 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. 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. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. 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 O(n^4) , however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an O(n^3) running time. Ford and Fulkerson extended the method to general maximum flow problems in the form of the Ford–Fulkerson algorithm.

Back to article

Article summary

The Hungarian algorithm or 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. 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. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. 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 O(n^4) , however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an O(n^3) running time. Ford and Fulkerson extended the method to general maximum flow problems in the form of the Ford–Fulkerson algorithm.

Key claims

  1. publication date: 1955 — source: Wikipedia · confidence 0.95
  2. publication date: 1890 — source: Wikipedia · confidence 0.95

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. The record states that the publication date is "1955". What evidence would count against this claim?
  3. The record states that the publication date is "1890". What evidence would count against this claim?
  4. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  5. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

  1. Wikipedia https://en.wikipedia.org/w/index.php?oldid=1375874851

Key claims and bibliography are generated from the same tracked claims and sources as the article page.