Zur
  Seite der TU

Seminar: Geometrische Varianten kombinatorischer Optimierungsprobleme

Zur Seite des Instituts für Mathematik
 

Wintersemester 2006

 
LV-Nr.: 0230 L 323
 
Dr. Ralf Borndörfer    und     Prof. Dr. Martin Grötschel
 


voronoi diagram    Germany TSPs    hull approach


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: Bei der Literatursuche sind folgende Links nützlich:


Termine

Das Seminar wird als Blockseminar am
durchgeführt (Lageplan).

Ein Termin mit Kurzvorträgen von jeweils 5 Minuten Dauer findet am
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

  1. 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])

  2. 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])

  3. Mathias Kinder: Der Separator-Satz
    A Separator Theorem for Planar Graphs (Lipton & Tarjan [1977])

    Applications of a Planar Separator Theorem (Lipton & Tarjan [1980])

  4. Christian Schumann: Maximale Flüsse in planaren Graphen
    Maximum (s,t)-flows in planar network in O(n log n) time (Weihe [1994])

  5. 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])

  6. Andreas Wiese: Approximationsalgorithem für NP-vollständige Probleme auf planaren Graphen
    Approximation Algorithms for NP-complete Problems on Planar Graphs (Baker [1994])

  7. Jonas Schweiger: Hamiltonsche Wege in planaren Graphen
    Exact algorithms for the Hamiltonian cycle problem in planar graphs (Deinecko, Klinz & Woeginger [2006])

  8. 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])

  9. 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
Borndoerfer
Dr. Ralf Borndörfer n.V. ZIB 84185-243 borndoerferzib.de
Groetschel
Prof. Dr. Martin Grötschel n.V. MA 302 84185-210 groetschelzib.de


Valid HTML 4.0!Zuletzt aktualisiert: 18. Januar 2007