Hat Jacobi den ungarischen Algorithmus für das Zuordnungsproblem über ein Jahrhundert vor König und Egerváry erfunden?

Es stimmt. Wikipedia verlinkt auf die Website von Ollivier, die sowohl die posthume Originalveröffentlichung in lateinischer Sprache, De investigando ordine systematis aequationum differentialum vulgarium cujuscunque , als auch ihre englische Übersetzung, About the Research of the Order of a System of Arbitrary Ordinary Differential Equations, von Ollivier selbst enthält . Leider spiegelt sich die Navigation innerhalb der Website nicht in den URLs wider, sodass Sie oben links auf Übersetzungen klicken müssen, um sie anzuzeigen. Ollivier ist derjenige, der es "gefunden" hat, und er beschreibt die vollständige Geschichte des Problems in Jacobis Bindung. Übertragung und Vergessen eines mathematischen Begriffs :

„ Jacobi selbst ist möglicherweise der erste, der seine eigene Arbeit vergessen hat. Laut Koenigsberger ([13]) wurden seine Manuskripte zu diesem Thema um 1836 geschrieben und sollten Teil eines aufgegebenen Projekts langer Abhandlungen über Differentialgleichungen sein. Ein Teil dieser Arbeit wurde in seine großartige Arbeit über den letzten Multiplikator aufgenommen, aber der Gebundene selbst wurde zu seinen Lebzeiten nie veröffentlicht.

[...] Jacobis Witwe übergab die von ihm hinterlassenen Manuskripte an Dirichlet, der mit seinen Freunden Borchardt und Joachimsthal begann, an ihrer Veröffentlichung zu arbeiten. Von dieser Arbeit sind nur sehr wenige Dokumente erhalten, und die beste Quelle scheint Koenigsberger zu sein ([13]). Es scheint, dass das Papier in großer Unordnung war ... Borchardt vertraute Sigismund Cohn, der an der Veröffentlichung einiger anderer Manuskripte von Jacobi arbeitete, die Dokumente an, die sich auf die Bindung bezogen ... Nach seinem Tod wurde die Arbeit von Borchardt fortgesetzt, der veröffentlichte 1865 die 1. Arbeit [8] in seiner Zeitschrift. Die zweite [9] wurde 1866 von Clebsch im Band Vorlesungen über Dynamik ([FD]) veröffentlicht. Diese wurde von Sofya Kovalevskaya in einer ihrer berühmtesten Arbeiten zitiert ([16]) im Jahr 1875. "

Für Details zum Zuordnungsproblem selbst und dem bereits Jacobi bekannten "ungarischen" Algorithmus zu seiner Lösung siehe Jeno Egervary: from the origins of the Hungarian algorithm to satellite communication :

„ Jacobi führt eine Schranke in der Größenordnung eines Systems von ein$m$gewöhnliche Differentialgleichungen in$m$Unbekannten, und stellt fest, dass seine Berechnung auf folgendes Problem reduziert werden kann ... bei dem jedoch das Zuordnungsproblem leicht zu erkennen ist:

Arrangieren$nn$willkürliche Zahlen$h^{(i)}_k$in einer quadratischen Tabelle, so dass es n horizontale Reihen und n vertikale Reihen mit jeweils n Zahlen gibt. Unter diesen Nummern wollen wir auswählen$n$Transversalen, d. h. alle in verschiedenen horizontalen und vertikalen Reihen angeordnet, die in ausgeführt werden können$1\cdot2\cdots n$Wege; Unter all diesen Wegen möchten wir einen finden, der die maximale Summe von ergibt$n$ausgewählte Zahlen.)

Jacobi hat nicht nur das AP definiert, sondern, was noch wichtiger ist, er hat einen polynomiellen Algorithmus zu seiner Lösung angegeben. Obwohl eine gründliche Analyse dieser Methode noch nicht geliefert wurde, haben Ollivier und Sadik [29] kürzlich festgestellt, dass sie im Wesentlichen mit dem ungarischen Algorithmus identisch ist, und damit die Ergebnisse, die wir in den vorherigen Abschnitten untersucht haben, um viele Jahrzehnte vorweggenommen. Wie Kuhn [24] witzig bemerkt, ist dies eine weitere Anwendung von Stiglers Namensgebergesetz: Keine wissenschaftliche Entdeckung wird nach ihrem ursprünglichen Entdecker benannt (Stigler [34], siehe auch Kuhn [23]) .