Referencias tempranas para la optimización discreta

(Disculpas si esto está fuera de lugar o es demasiado amplio. Estoy abierto a sugerencias sobre cómo reformularlo).

Estoy interesado en rastrear la historia "antigua" de los algoritmos de flujo máximo y los algoritmos de optimización discretos en general. Ford-Fulkerson es mi hombre de paja como punto de partida. ¿Cuáles fueron los avances significativos anteriores a eso? ¿Qué tan lejos podemos llegar sin dejar de argumentar razonablemente que alguien estaba trabajando en max-flow? ¿Qué hay de los algoritmos gráficos? ¿Qué tal la optimización discreta en general?

También estaría feliz de obtener referencias a lugares donde se discute esto.

Por lo general, Schrijver proporciona una buena fuente de historia. Puedes mirar los siguientes libros y un artículo.

• Alexander Schrijver. Optimización combinatoria: poliedros y eficiencia. Springer 2003.
• Alexander Schrijver. Teoría de la programación lineal y entera. Wiley 1998.
• Alexander Schrijver. Sobre la historia del transporte y los problemas de flujo máximo. Programación matemática 91 (3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
• Alexander Schrijver. Sobre la historia de la optimización combinatoria (hasta 1960). Manual de optimización discreta, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf

La mayoría de la gente cita el papel de 1741 "Puentes de Königsburg" de Euler como el algoritmo gráfico más antiguo. Desafortunadamente, Euler en realidad no describe su algoritmo en detalle, pero solo da un ejemplo poco entusiasta:

“Cuando se ha determinado que se puede hacer un viaje así, todavía hay que encontrar cómo se debe organizar. Para esto utilizo la siguiente regla: dejar que esos pares de puentes que conducen de un área a otra se eliminen mentalmente, reduciendo así considerablemente el número de puentes; Entonces es una tarea fácil construir la ruta requerida a través de los puentes restantes. y los puentes que se han eliminado no alterarán significativamente la ruta encontrada, como quedará claro después de pensarlo un poco. Por lo tanto, no creo que valga la pena dar más detalles sobre el hallazgo de las rutas. "

La primera prueba completa de que todos los gráficos conectados tienen recorridos eulerianos aparentemente se debe a Heirholzer más de un siglo después.

• Leonhard Euler. Solutio problematis ad geometriam situs pertinente. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Presentado en la Academia de San Petersburgo el 26 de agosto de 1735. Reimpreso en Opera Omnia 1 (7): 1–10.

• Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6: 30–32, 1873.