Did Jacobi invent the Hungarian algorithm for the assignment problem over a century before Kőnig and Egerváry?

Wikipedia says:

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.

The provided reference gives no support to the statement. Do you know the story? Is it true? Who discovered it?

• In that reference you click in the left top corner on "Presentation". I suppose it answers your question. Translations of Jacobi papers in question are also there. – Alexandre Eremenko Nov 7 '19 at 22:56

1 Answer

It is true. Wikipedia links to the website of Ollivier, which hosts both the original posthumous publication in Latin, De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, and its English translation, About the Research of the Order of a System of Arbitrary Ordinary Differential Equations, by Ollivier himself. Unfortunately, navigation within the site is not reflected in the urls, so you have to click on Translations on the top left to see them. Ollivier is the one who "found" it, and he describes the full story of the problem in Jacobi's bound. Transmission and oblivion of a mathematical notion:

"Jacobi himself is possibly the first to have forgotten his own work. According to Koenigsberger ([13]), his manuscripts on this subject were written around 1836 and were intended to be a part of a forsaken project of long paper on differential equations. Part of this work was incorporated in his great paper on the last multiplier, but the bound himself was never published in his lifetime.

[...] Jacobi's widow gave the manuscripts he left to Dirichlet who began to work for their publication with his friends Borchardt and Joachimsthal. Very few documents remain from that work and the best source seems to be Koenigsberger ([13]). It seems that the paper were in great disorder... Borchardt entrusted Sigismund Cohn, who worked on the publication of some others manuscripts of Jacobi, with the documents related to the bound... After his death, the work was continued by Borchardt who published the 1st paper [8] in his journal in 1865. The second [9] was published by Clebsch in the volume Vorlesungen uber Dynamik ([FD]) in 1866. This one was quoted by Sofya Kovalevskaya in one of her most famous papers ([16]) in 1875."

For details on the assignment problem itself and the "Hungarian" algortihm for solving it, known already to Jacobi, see Jeno Egervary: from the origins of the Hungarian algorithm to satellite communication:

"Jacobi introduces a bound on the order of a system of $$m$$ ordinary differential equations in $$m$$ unknowns, and observes that its computation can be reduced to the following problem... in which however the assignment problem is easily recognized:

Arrange $$nn$$ arbitrary numbers $$h^{(i)}_k$$ in a square table so that there are n horizontal series and n vertical series, each having n numbers. Among these numbers, we want to select $$n$$ transversals, i.e., all placed in different horizontal and vertical series, which may be done in $$1\cdot2\cdots n$$ ways; among all these ways, we want to find one that gives the maximum sum of the $$n$$ selected numbers.)

Not only Jacobi defined the AP, but, more importantly, he gave a polynomial- time algorithm to solve it. Although a thorough analysis of this method has not been provided yet, Ollivier and Sadik [29] recently observed that it is essentially identical to the Hungarian algorithm, thus anticipating by many decades the results we have examined in the previous sections. As wittily observed by Kuhn [24], this makes another application of Stigler's law of eponymy": No scientific discovery is named after its original discoverer (Stigler [34], see also Kuhn [23])."