Ungarische Methode

Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der Linearen Optimierung formuliert werden, die ungarische Methode ist dann eine angepasste primal-duale Lösungsmethode. Die originale Implementierung hatte eine Komplexität von ${\displaystyle O(n^{4})}$, durch geeignete Datenstrukturen und optimierte Unterroutinen konnte diese aber auf ${\displaystyle O(n^{3})}$ gesenkt werden.

Die Ungarische Methode wurde 1955 von Harold W. Kuhn unter Einbeziehung vorheriger Ideen der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry entwickelt und von James Munkres 1957, einer Analyse der Laufzeit folgend, verbessert.

Das Zuordnungsproblem wurde schon im 19. Jahrhundert von Carl Gustav Jacob Jacobi gelöst. Die Lösung wurde im Jahr 1890 veröffentlicht.

1. ↑ H. W. Kuhn (1955): The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, S. 83–97.
2. ↑ J. Munkres (1957): Algorithms for the Assignment and Transportation Problems, Journal of the Society of Industrial and Applied Mathematics, Vol. 5 Nr. 1, S. 32–38.
3. ↑ François Ollivier: Looking for the order of a system of arbitrary ordinary differential equations. In: Applicable Algebra in Engineering, Communication and Computing. Band 20, Nr. 1, 1. April 2009, ISSN 1432-0622, S. 7–32, doi:10.1007/s00200-009-0087-3. 
4. ↑ Carl Gustav Jacob Jacobi: De investigando ordine systematis æquationum differentialium vulgarium cujuscunque