Zur
  Seite der TU

Seminar: Matchings, Flüsse und Verallgemeinerungen

Zur Seite des Instituts für Mathematik
 

Wintersemester 2003

 
LV-Nr.: 0230 L 316
 

Prof. Dr. Martin Grötschel    und    Dr. Frank Lutz
 


Inhalt

Es werden einige Kapitel aus dem dreibändigen Lehrbuch Combinatorial Optimization (Springer, 2003) von Alexander Schrijver behandelt.

Als zusätzliche Quellen empfehlen wir die Bücher

R.K. Ahuja, T.L. Magnanti, J.B. Orlin:
Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver:
Combinatorial Optimization, Wiley, 1998

B. Korte, J. Vygen:
Combinatorial Optimization, Theory and Algorithms, Springer, 2000 (2. Auflage, 2002)


Voraussetzungen

Lineare Algebra, Graphen- und Netzwerkalgorithmen (ADM I).


Hinweise zu den Vorträgen

Richtlinien für die Vortragsgestaltung und die Scheinvergabe:


Veranstaltungstermin

Das Seminar wird als Blockseminar am Wochenende 23.-25. Januar 2004 im Seminarraum 2006 des Konrad-Zuse-Zentrum durchgeführt (Lageplan).

Am 26. Januar 2004, 14:15 Uhr, wird das Seminar mit einem Vortrag von Prof. Alexander Schrijver im European Graduate Program ``Combinatorics, Geometry, and Computation'' an der TU Berlin, MA 041, abgeschlossen:

Alexander Schrijver
(CWI und University of Amsterdam)

Open problems in combinatorial optimization

We discuss some open problems given in my recent book
``Combinatorial Optimization: Polyhedra and Efficiency''.
We plan to select from each of the eight parts of the
book one problem, and give background and motivation.



Programm


Freitag, 23.01.2004

09:00 Sebastian Behrendt: Cardinality bipartite matching and vertex cover (Ch. 16)
10:00 Franziska Ryll: Weighted bipartite matching and the assignment problem (Ch. 17)
11:00 Pause
11:10 Hacer Igde: Linear programming methods and the bipartite matching polytope (Ch. 18, I)
12:10 Mittagspause
13:30 Manuel Kutschka: Bipartite edge-colouring (Ch. 20)
14:30 Jens Miethe: Bipartite b-matchings and transportation (Ch. 21)
15:30 Pause
16:00 Anton Telle: Transversals (Ch. 22)


Samstag, 24.01.2004

09:00 Nadine Abboud: Cardinality nonbipartite matching (Ch. 24, I)
10:00 Julia Däumer: Cardinality nonbipartite matching (Ch. 24, II)
11:00 Pause
11:10 Christian Raack: The matching polytope (Ch. 25, I)
12:10 Mittagspause
13:30 Marika Neumann: The matching polytope (Ch. 25, II)
14:30 Alexander Klar: Weighted nonbipartite matching algorithmically (Ch. 26)
15:30 Pause
16:00 Ronald Wotzlaw: T-joins, undirected shortest paths, and the Chinese postman (Ch. 29)


Sonntag, 25.01.2004

09:00 Suganya Murugaiah: 2-matchings, 2-covers, and 2-factors (Ch. 30, I)
10:00 Kati Wolter: 2-matchings, 2-covers, and 2-factors (Ch. 30, II)
11:00 Pause
11:10 Timo Berthold: b-matchings and capacitated b-matchings (Ch. 31 & 32, I)
12:10 Mittagspause
13:30 Annegret Dix: b-matchings and capacitated b-matchings (Ch. 31 & 32, II)
14:30 Harald Schülzke: The dimension of the perfect matching polytope (Ch. 37)
15:30 Pause
16:00 Myriam Schade: Cliques, stable sets, and colouring (Ch. 64 & 68)
17:30 Luise



Kontakte

 
Sprechstunde
Raum Telefon email
Prof. Dr. Martin Grötschel n.V. MA 302 84185-210 groetschelzib.de
Dr. Frank Lutz Do 10:00 - 11:30 MA 624 314-25 751 lutzmath.tu-berlin.de


Valid HTML 4.0! Zuletzt aktualisiert: 28. Januar 2004