Fortgeschrittene Lineare Optimierung WS 06/07

Aktuelle Informationen und Hinweise

• Die Klausur findet am 21.2.07 (Mittwoch) in der Zeit von 9.30-12.30 Uhr im PK 11.1 statt.
• Das zwölfte Übungsblatt ist da.
• Hier findet man das in der Hausaufgabe zitierte Skript (1,1 MB). Kapitel 12 beschäftigt sich mit der Ellipsoidmethode.
• Die Vorlesung am Dienstag ist in den SN 20.2 verlegt worden.
• Der Semesterapparat ist zusammengestellt (siehe unten).
• Es lohnt sich, diese Seite im Auge zu behalten!
• Die Übungsblätter werden über diese Seite verfübgar sein - siehe unten.
• Erste Vorlesung am 2. November; erste große Übung am 6. November; kleine Übungen ab 13. November.
• Literaturhinweise hängen unten.
• Für diese Vorlesung gibt es eine eigene Mailingliste. (Die Liste aus dem Vorsemester wird fortgeführt!) Wer dort noch nicht angemeldet war: Das Anmeldeformular findet man hier. Nach der Anmeldung erhält man eine Mail an die eingegebene Adresse. Damit man sich nur selbst anmelden kann, muss man von dieser Adresse noch eine Bestätigung abschicken. Das klappt normalerweise ganz einfach, indem man "reply" drueckt und die Sache abschickt. Bei technischen Schwierigkeiten bitte eine Mail an mich!

Allgemeine technische Hinweise

• Die Vorlesung wendet sich an Studierende im Hauptstudium. Kenntnisse aus der ``Einführung in die Optimierung'' werden zwar vorausgesetzt, sind aber nur an einzelnen Stellen notwendig.
• Die Scheinvergabe erfolgt aufgrund einer Klausur am Ende des Semesters und der auf den Hausaufgabenblättern erzielten Punkten.
• Details zum Übungsbetrieb werden demnächst bekanntgegeben.
• Falls es speziellere Fragen, individuelle Schwierigkeiten oder Unklarheiten gibt, so bitte ich ganz einfach um eine Nachfrage; das geht sehr gut per Mail, aber auch in Person nach der Vorlesung oder in meiner Sprechstunde. (Gerade Unklarheiten betreffen oft noch mehrere Teilnehmer, daher bin ich für Nachfragen durchaus dankbar!)

Inhaltliche Hinweise

• Matrixspiele
• Revidierter Simplex
• Netzwerk-Simplex
• Polyedertheorie
• Ellipsoidmethode

Termine

Sprechstunden:

Übungsblätter

Literatur und Links

• Im Buch von Korte und Vygen findet man auf den Seiten 397-406 Erläuterungen zum Rucksack-Problem.
• Hier findet man den Artikel "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time" von Spielman und Teng; hier den von Vershynin, in dem die Schranke für Laufzeit der Simplexmethode noch verbessert wird.