Polyhedral Combinatorics (ADM III)	Englisch
	Sommersemester 2010

Aktuell   Inhalt   Voraussetzungen   Zeiten   Kontakte   Literatur   Vorlesungsskriptum   Hinweise  

Diese Vorlesung wird im Rahmen der Berlin Mathematical School angeboten und auf Englisch gehalten. Die Polyedrische Kombinatorik nutzt Methoden der Polyedertheorie und der Linearen Algebra, um kombinatorische Probleme zu lösen. Die grundlegende Idee dabei ist, ein kombinatorisches Problem in ein Polyeder-Problem umzuwandeln und dieses zu lösen. Die Studenten sollen in die Lage versetzt werden, diese Methodologie in praxisrelevanten Beispielen anzuwenden und wichtige Ergebnisse zu beweisen. Der Fokus liegt dabei auf der Lösung NP-schwerer kombinatorischer Optimierungsprobleme.

Aktuelles

Inhalt

Es werden bedeutende Probleme der Kombinatorik betrachtet, wie z. B. das Travelling-Salesman-Problem, Max-Cut-Verfahren, Linear Ordering,Stabile-Mengen-Probleme (einschließlich perfekter Graphen und der Theta-Körper) sowie das Matching-Problem. Wir werden z. B. die Facettenstruktur der Polytope, die mit diesen Problemen verbunden sind, untersuchen und zeigen, wie man Schnittebenen-Techniken zur Lösung dieser Optimierungsprobleme einsetzen kann. Beispiele aus der realen Welt verdeutlichen die Probleme, die sich dabei in der Praxis ergeben und die zu lösen sind.

Voraussetzungen

Zeiten

Kontakte

		Sprechstunde	Raum	Telefon	email
TU-Büro	Martin Grötschel	n.V.	MA 302	314-23266	groetschelzib.de (ZIB)
ZIB-Büro	Martin Grötschel	n.V.	R 3026	84185 210	groetschelzib.de
Sekretariat (TU):	Claudia Ewel	n.V.	MA 310	314-28 478	ewelmath.tu-berlin.de
Sekretariat (ZIB):	Bettina Kasse	n.V.	3025	84185-209	kassezib.de

Literatur

• Schrijver, Alexander (2003), Combinatorial Optimization: Polyhedra and Efficiency: 3 Bde. (Algorithms and Combinatorics)
• M. Grötschel, L. Lovász, A. Schrijver (1993), Geometric Algorithms and Combinatorial Optimization, 2nd corrected edition

Vorlesungsskriptum

Hinweise

Zuletzt aktualisiert: 18. Mai 2010