Nahezu jedes Kombinatorische Optimierungsproblem lässt sich als ganzzahliges lineares Programm beschreiben; für einige ist auch eine Beschreibung als Lineares Programm (ohne Ganzzahligkeitsbedingung) bekannt. Wir untersuchen solche Beschreibungen und leiten hieraus einige wichtige Sätze der Kombinatorischen Optimierung sowie die polynomielle Lösbarkeit einiger Probleme ab. Unter anderem werden aufspannende Bäume, Arboreszenzen, Flüsse, Matchings, T-joins, Matroide und das TSP betrachtet.
| Vorkenntnisse: | Grundbegriffe aus der Linearen Optimierung (z. B. Dualitätssatz) und Graphentheorie werden vorausgesetzt; gewisse Kenntnisse in Kombinatorischer Optimierung sind hilfreich. |
| Ort: | Hörsaal Lennéstr. 2 |
| Zeit: | Montags 12:30-14:00 Uhr |
| Beginn: | 28.10.1997. |
J. Vygen