Montag, 10:00-12:00 Uhr MA 650
Freitag, 10:00-12:00 Uhr MA 650

Approximationsalgorithmen für kombinatorische Optimierungsprobleme liefern in polynomieller Zeit zulässige Lösungen, die beweisbar ``gut'' sind. Derartige Algorithmen werden üblicherweise für NP-schwere Probleme entworfen, da polynomielle Algorithmen zu deren exakter Lösung vermutlich nicht existieren. Obwohl das Gebiet der Approximationsalgorithmen seit etwa 1960 (vor dem Konzept der NP-Vollständigkeit!) existiert, so hat die Entwicklung von Approximationsalgorithmen gerade in den letzten Jahren aufsehenerregende Fortschritte gemacht.

``The methods used for designing such [approximation] algorithms tend to be rather problem specific, although a few guiding principles have been identified and can provide a useful starting point'' (M. R. Garey and D. S. Johnson, 1979).

Das Zitat belegt, daß vor einigen Jahren der Entwurf von Approximationsalgorithmen ad hoc und stark von der Struktur des jeweiligen Problems abhängig war. In den letzten Jahren sind jedoch eine Vielzahl neuer Techniken für den Entwurf solcher Algorithmen entdeckt und erfolgreich auf diverse kombinatorische Optimierungsprobleme angewendet worden. In dieser Veranstaltung werden diese Techniken und die mit ihnen erzielten Resultate diskutiert. Dazu zählen insbesondere:

• metrische Methoden (u. a. für multi-cuts, balanced cuts, minimum flux cuts),
  
• randomisierte Methoden (u. a. für VLSI design, max sat, max cut),
  
• semi-definite Methoden (u. a. für max cut, coloring),
  
• primal-duale Methoden (u. a. für network design problems).

Lineare Optimierung sowie Kombinatorische Optimierung. Paralleles Hören der Vorlesung Kombinatorische Optimierung bei Herrn Prof. Möhring ist ausreichend!

Rücksprache

Veranstaltung im Studienschwerpunkt "Algorithmische Diskrete Mathematik"; gleichermaßen für Mathematiker sowie für Techno- und Wirtschaftsmathematiker geeignet.

Die erste Vorlesung findet am Freitag, den 25. Oktober 1996, um 10:15 Uhr statt.