Frühe Referenzen zur diskreten Optimierung

9

(Entschuldigung, wenn dies falsch oder zu weit gefasst ist. Ich bin offen für Vorschläge zur Neuformulierung.)

Ich bin daran interessiert, die "alte" Geschichte der Max-Flow-Algorithmen und der diskreten Optimierungsalgorithmen im Allgemeinen zurückzuverfolgen. Ford-Fulkerson ist mein Strohmann eines Ausgangspunkts. Was waren die wesentlichen Fortschritte davor? Wie weit können wir zurückgehen, während wir noch ein vernünftiges Argument dafür vorbringen können, dass jemand an Max-Flow gearbeitet hat? Wie wäre es mit Graph-Algorithmen? Wie wäre es mit diskreter Optimierung im Allgemeinen?

Ich würde mich auch über Hinweise auf Orte freuen, an denen dies diskutiert wird.

ds.algorithms graph-algorithms ho.history-overview dan_x
quelle

Antworten:

14

Normalerweise bietet Schrijver eine gute Quelle für die Geschichte. Sie können sich die folgenden Bücher und einen Artikel ansehen.

  • Alexander Schrijver. Kombinatorische Optimierung: Polyeder und Effizienz. Springer 2003.
  • Alexander Schrijver. Theorie der linearen und ganzzahligen Programmierung. Wiley 1998.
  • Alexander Schrijver. Zur Geschichte des Transports und zu Problemen mit maximalem Durchfluss. Mathematical Programming 91 (3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
  • Alexander Schrijver. Zur Geschichte der kombinatorischen Optimierung (bis 1960). Handbook of Discrete Optimization, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf
Yoshio Okamoto
quelle
1
+1 für Schrijver. Ich fügte eine vierte empfohlene Quelle hinzu, die auf frühe Arbeiten von Frobenius [1912] und Kőnig [1915] zum zweigliedrigen Matching, Boruvka [1926] über minimale Spannbäume und Menger [1927] zu seinem sogenannten " arc-Theorem" verweist. und wieder [1930] zum Problem der reisenden Verkäufer und Tolstoi [1930] zum Transportproblem. n
Jeffs
@ Jɛ ff E: Vielen Dank für den Zusatz.
Yoshio Okamoto
Vielen Dank. Der letzte Teil der Geschichte der kombinatorischen Optimierung ist genau das, wonach ich gesucht habe.
dan_x
7

Die meisten Leute zitieren Eulers Papier "Bridges of Königsburg" von 1741 als den ältesten Graph-Algorithmus. Leider beschreibt Euler seinen Algorithmus nicht im Detail, sondern gibt nur ein halbherziges Beispiel:

„Wenn festgestellt wurde, dass eine solche Reise möglich ist, muss man noch herausfinden, wie sie arrangiert werden soll. Hierfür verwende ich die folgende Regel: Lassen Sie die Brückenpaare, die von einem Bereich zum anderen führen, mental entfernen, wodurch die Anzahl der Brücken erheblich verringert wird. Es ist dann eine einfache Aufgabe, die erforderliche Route über die verbleibenden Brücken zu konstruieren. und die Brücken, die entfernt wurden, werden die gefundene Route nicht wesentlich verändern, wie nach einigem Nachdenken klar wird. Ich halte es daher nicht für sinnvoll, weitere Einzelheiten zur Ermittlung der Routen anzugeben. ”

Der erste vollständige Beweis, dass alle sogar verbundenen Graphen Eulersche Touren haben, ist offenbar mehr als ein Jahrhundert später auf Heirholzer zurückzuführen.

  • Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae 8: 128–140, 1741. Am 26. August 1735 an die St. Petersburg Academy übergeben. Nachdruck in Opera Omnia 1 (7): 1–10.

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

Jeffε
quelle