Seminar: Geometrische Varianten kombinatorischer Optimierungsprobleme (WS 2006)

	Seminar: Geometrische Varianten kombinatorischer Optimierungsprobleme
	Wintersemester 2006

LV-Nr.: 0230 L 323

Dr. Ralf Borndörfer und Prof. Dr. Martin Grötschel

Aktuell

18.01.07: Samstag ist frei
18.01.07: Programm liegt fest
12.01.07: Techniktest 14:00-15:00 am Konrad-Zuse-Zentrum im Seminarraum R 2006
24.10.06: Termine liegen fest
23.10.06: Vergebene Themen, Links zur Literaturrecherche

Inhalt

In dem Seminar geht es um klassische kombinatorische Optimierungsprobleme, bei denen eine zusätzliche geometrische Komponente hinzukommt. Kürzeste Wege in planaren Graphen, das TSP in der Ebene, Lineare Programmierung im R2 usw. sind Beispiele für solche Probleme. Kann man die Geometrie ausnutzen, um Probleme besser zu verstehen oder bessere Algorithmen zu entwickeln? Ziel des Seminar ist es, anhand verschiedener Fälle, in denen dies gelungen ist, einen Einblick in die Möglichkeiten und Grenzen der dabei verwendeten Techniken zu gewinnen.

Voraussetzungen

Grundkenntnisse in Graphen- und Netzwerkalgorithmen und kombinatorischer Optimierung. Für einige Themen sind Kenntnisse in linearer und ganzzahliger Optimierung notwendig.

Hinweise zu den Vorträgen

Richtlinien für die Vortragsgestaltung und die Scheinvergabe:

Die wesentliche Leistung ist ein Vortrag von ca. 60 Minuten über das zugeteilte Thema. Im Vortrag sollen in verständlicher Form wichtige Ergebnisse des (für den Vortrag zentralen) Artikels vorgestellt werden. Ausgewählte Beweise sollen erklärt werden.
Die Vortragsform und -medien kann jeder frei wählen. Als Vortragsmedien stehen Tafel, Overhead-Projektor und Beamer zur Verfügung. Insbesondere bei Beamerbenutzung sollte die Technik vorher geprüft werden.
Zum Vortragstermin ist von den Vortragenden eine etwa 5-seitige Ausarbeitung zum Thema vorzulegen. Diese wird an alle Seminarteilnehmerinnen und Seminarteilnehmer verteilt. In dieser Ausarbeitung sollen wesentliche Definitionen und Ergebnisse zusammengefasst werden. Die Ausarbeitung soll in ``Publikationsqualität'' vorliegen. Es wird empfohlen, die Ausarbeitung mit Hilfe von LaTeX zu schreiben. Für LaTeX-Unkundige ist dies vielleicht ein guter Zeitpunkt, sich LaTeX anzueignen, da man im mathematischen Leben kaum darum herumkommt. (Empfehlenswerte Literatur für Einsteiger ist der erste Band der LaTeX-Serie von Helmut Kopka, erschienen bei Addison-Wesley. Bitte achten Sie darauf, dass es sich um eine ``aktuelle'' Version handelt, die LaTeX2e behandelt.)

Bei der Literatursuche sind folgende Links nützlich:

Mathematische Artikel: Zentralblatt
Mathematische Webseiten: MathSearch
Mathematische und informatische Abstracts/Bibliographie: CiteSeer
Informatische Artikel/Bibliographie: ACM Portal
Wissenschaftliches Googlen: GoogleScholar

Termine

Das Seminar wird als Blockseminar am

Fr/Sa, den 19./20.01.07 jeweils von 09:00-18:00 im Seminarraum 2006 am Konrad-Zuse-Zentrum

durchgeführt (Lageplan).

Ein Termin mit Kurzvorträgen von jeweils 5 Minuten Dauer findet am

Montag, dem 04. Dezember 2006 ab 16:00 an der TU Berlin im Raum MA 313

statt.

Programm

Freitag, 19. Januar 2007

09:00-10:00    Sorana Götzke: Planare Graphen
10:00-11:00    Anja Trillhaase: Maximale Schnitte in planaren Graphen
11:00-12:00    Mathias Kinder: Der Separator-Satz
12:00-13:00    Pause
13:00-14:00    Christian Schumann: Maximale Flüsse in planaren Graphen
14:00-15:00    Max Klimm: Disjunkte homotope Pfade in planaren Graphen
15:00-16:00    Andreas Wiese: Approximationsalgorithem für NP-vollständige Probleme auf planaren Graphen
16:00-16:30    Pause
16:30-17:30    Jonas Schweiger: Hamiltonsche Wege in planaren Graphen
17:30-18:30    Maciej Warszawski: Kürzeste Wege mit einer Nebenbedingung
18:30-19:30    Martin Sieg: Voronoi-Diagramme und Delaunay-Triangulationen
19:30-20:00    Scheinvergabe

Themen

Sorana Götzke: Planare Graphen
Planare Graphen: Definition, Geometrische Dualität, etc. (Referenz ist selbst zu beschaffen)
A Short Proof of Kuratowski's Planarity Criterion (Makarychev [1995])
Euler's Polyhedral Formula, Kap. 5 in Graph Theory (Biggs, Lloyd & Wilson [1976])
Anja Trillhaase: Maximale Schnitte in planaren Graphen
Finding a maximum cut of a planar graph in polynomial time (Hadlock [1975])
Comments on F. Hadlock's Paper: Finding a maximum cut of a planar graph in polynomial time (Aoshima & Iri 1977)
Unifying maximum cut and minimum cut of a planar graph (Shih, Wu & Kuo [1990])
Mathias Kinder: Der Separator-Satz
A Separator Theorem for Planar Graphs (Lipton & Tarjan [1977])
Applications of a Planar Separator Theorem (Lipton & Tarjan [1980])
Christian Schumann: Maximale Flüsse in planaren Graphen
Maximum (s,t)-flows in planar network in O(n log n) time (Weihe [1994])
Max Klimm: Disjunkte homotope Pfade in planaren Graphen
Routing and Timetabling by Toplogical Search (Schrijver 1998)
Disjoint Homotopic Paths and Trees in a Planar Graph (Schrijver [1991])
Andreas Wiese: Approximationsalgorithem für NP-vollständige Probleme auf planaren Graphen
Approximation Algorithms for NP-complete Problems on Planar Graphs (Baker [1994])
Jonas Schweiger: Hamiltonsche Wege in planaren Graphen
Exact algorithms for the Hamiltonian cycle problem in planar graphs (Deinecko, Klinz & Woeginger [2006])
Martin Sieg: Voronoi-Diagramme und Delaunay-Triangulationen
Computational Geometry (WWW)
Voronoi Diagrams and Delaunay Triangulations (Fortune [2004]), in Handbook of Discrete and Computational Geometry (Goodman & O'Rourke [2004])
Proximity: Fundamental Algorithms, Kap. 5 in Computational Geometry (Preparata & Shamos [1985])
Maciej Warszawski: Kürzeste Wege mit einer Nebenbedingung
Resource Constrained Shortest Paths (Mehlhorn & Ziegelmann [2000])
Constrained Shortest Paths and Related Problems (Ziegelmann [2001])

Kontakte

	Sprechstunde	Raum	Telefon	email
Dr. Ralf Borndörfer	n.V.	ZIB	84185-243	borndoerferzib.de
Prof. Dr. Martin Grötschel	n.V.	MA 302	84185-210	groetschelzib.de

Zuletzt aktualisiert: 18. Januar 2007

Seminar: Geometrische Varianten kombinatorischer Optimierungsprobleme

Wintersemester 2006