*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 15
Dienstag, 19.09.2000, 14.30–14.50 Uhr, WIL C 103

Maximale Schnitte, maximal unabhängige Mengen und Brücken zur Geometrie

Andreas Brieden, TU München

Eine Vielzahl von Ergebnissen zur effizienten Approximierbarkeit algorithmischer Probleme der Graphentheorie hat in der jüngeren Vergangenheit für Aufsehen gesorgt. Die Bestimmung maximaler Schnitte mithilfe des “random-hyperplane”-Algorithmus (Goemans, Williamson) sowie die “optimale” Nichtapproximierbarkeitsaussage Håstads für die Bestimmung maximaler, unabhängiger Mengen in Graphen sind dafür zwei prominente Beispiele.

Bei näherer Untersuchung ergeben sich bei beiden Problemen interessante Beziehungen zu Optimierungsproblemen der Geometrie, auf die im Vortrag näher eingegangen wird.

Wird zum Beispiel mit einem gewichteten Graphen G ein spezielles Simplex S identifiziert, so entspricht die euklidische Dicke von S (Entfernung zweier paralleler, abstandsminimaler Hyperebenen, die S einschließen) gerade dem maximalen Schnitt in G. Dieser Zusammenhang liefert sowohl untere als auch obere Schranken für die effiziente Berechenbarkeit der Dicke von Simplexen.

Mithilfe der polyedrischen Kombinatorik kann die Bestimmung maximaler, unabhängiger Mengen auf die Maximierung von lp-Normen über Polytopen reduziert werden. Unter entsprechenden Annahmen zu Komplexitätsklassen ermöglicht diese Transformation den Beweis neuer Schranken für die effiziente Approximierbarkeit von lp-Einheitskugeln durch Polytope. Diese verbessern bekannte, mithilfe der geometrischen Analysis entwickelte Schranken.

(gemeinsame Arbeiten mit P. Gritzmann und V. Klee)