¿Jacobi inventó el algoritmo húngaro para el problema de asignación más de un siglo antes que Kőnig y Egerváry?

Es verdad. Enlaces de Wikipedia al sitio web de Ollivier, que alberga tanto la publicación póstuma original en latín, De investigando ordine systematis aequationum differenceum vulgarium cujuscunque , como su traducción al inglés, Acerca de la investigación del orden de un sistema de ecuaciones diferenciales ordinarias arbitrarias, del propio Ollivier. . Desafortunadamente, la navegación dentro del sitio no se refleja en las URL, por lo que debe hacer clic en Traducciones en la parte superior izquierda para verlas. Ollivier es quien lo "encontró", y describe la historia completa del problema en el límite de Jacobi. Transmisión y olvido de una noción matemática :

El mismo Jacobi es posiblemente el primero en haber olvidado su propio trabajo. Según Koenigsberger ([13]), sus manuscritos sobre este tema fueron escritos alrededor de 1836 y estaban destinados a ser parte de un proyecto abandonado de un largo artículo sobre ecuaciones diferenciales. Parte de este trabajo se incorporó a su gran artículo sobre el último multiplicador, pero el encuadernado nunca se publicó en vida.

[...] la viuda de Jacobi entregó los manuscritos que dejó a Dirichlet, quien comenzó a trabajar para su publicación con sus amigos Borchardt y Joachimsthal. Quedan muy pocos documentos de ese trabajo y la mejor fuente parece ser Koenigsberger ([13]). Parece que el papel estaba en gran desorden... Borchardt encomendó a Sigismund Cohn, quien trabajó en la publicación de algunos otros manuscritos de Jacobi, los documentos relacionados con la encuadernación... Después de su muerte, el trabajo fue continuado por Borchardt quien publicó el primer artículo [8] en su diario en 1865. El segundo [9] fue publicado por Clebsch en el volumen Vorlesungen uber Dynamik ([FD]) en 1866. Este fue citado por Sofya Kovalevskaya en uno de sus artículos más famosos. ([16]) en 1875. "

Para obtener detalles sobre el problema de asignación en sí y el algoritmo "húngaro" para resolverlo, ya conocido por Jacobi, consulte Jeno Egervary: desde los orígenes del algoritmo húngaro hasta la comunicación por satélite :

Jacobi introduce un límite en el orden de un sistema de$m$ecuaciones diferenciales ordinarias en$m$incógnitas, y observa que su cálculo se puede reducir al siguiente problema... en el que, sin embargo, el problema de asignación se reconoce fácilmente:

Arreglar$nn$números arbitrarios$h^{(i)}_k$en una mesa cuadrada de manera que hay n series horizontales y n series verticales, cada una con n números. Entre estos números, queremos seleccionar$n$transversales, es decir, todos colocados en diferentes series horizontales y verticales, que pueden hacerse en$1\cdot2\cdots n$maneras; entre todas estas formas, queremos encontrar una que dé la máxima suma de las$n$números seleccionados).

Jacobi no solo definió el AP, sino que, lo que es más importante, proporcionó un algoritmo de tiempo polinomial para resolverlo. Aunque todavía no se ha proporcionado un análisis exhaustivo de este método, Ollivier y Sadik [29] observaron recientemente que es esencialmente idéntico al algoritmo húngaro, por lo que se anticipa por muchas décadas a los resultados que hemos examinado en las secciones anteriores. Como observó ingeniosamente Kuhn [24], esto hace otra aplicación de la ley de eponimia de Stigler: "Ningún descubrimiento científico lleva el nombre de su descubridor original (Stigler [34], véase también Kuhn [23]). "