Seminar Matchings, Flüsse und Verallgemeinerungen (WS 2003)

	Seminar: Matchings, Flüsse und Verallgemeinerungen
	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:

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

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