Geometry of Cuts and Metrics (SS2011)

	Geometry of Cuts and Metrics (ADM III)
	Summer Semester 2011

LV-Nr.: 3236 L 293

Prof. Dr. Dr. h.c. mult. Martin Grötschel

News

In the Summer Semester 2011 I offer the two-hours lecture ADM III "Geometry of Cuts and Metrics" in English.

The first lecture will take place on April 12, 2011, 14:00-16:00 h, at TU Berlin, Institute of Mathematics, Straße des 17. Juni 136, room MA 742.

Cuts in graphs, metrics in vector spaces, cycles in matroids are mathematical objects that appear in many areas of mathematics and its applications and in quite diverse contexts. Students will learn in this class to study and approach these objects from a geometric point of view, in particular, via cones and polyhedra. One special aim is to obtain a better understanding of these polyhedra in order to be able to solve related optimization problems. The applications range from statistical mechanics, via VLSI design and measure theory to embeddability problems of finite metric spaces.

Requirements

The lecture will be based on the book by M. M. Deza, M. Laurent, Geometry of Cuts and Metrics, Springer 1997, and a number of research papers. Basic knowledge in Graph Theory and Linear and Integer Programming, such as taught in ADM I and II, is a prerequisite for this course. An excellent source for "background material" is the Schrijver book mentioned below.

Note

In the Summer Semester 2011 I also offer a seminar on "Cuts, Metrics and Matroids".

Times

There will be no tutorial and excersises.
Lecture: Each Tuesday (from April 12 to July 12, 2011)		14:00 - 16:00 h	MA 742

Contact

		consultation-hours	room	phone	email
Secretariat (TU):	Claudia Ewel	on appointment	MA 310	314-28 478	ewelmath.tu-berlin.de
Secretariat (ZIB):	Bettina Kasse	on appointment	3025	84185-209	kassezib.de

Literature

M. M. Deza, M. Laurent, Geometry of Cuts and Metrics, Springer 1997
Alexander Schrijver, Combinatorial Optimization (3 Volumes, A, B, C)

Lecture Notes

I do not offer lecture notes for this class but have prepared a summary of all topics covered with links to the literature where the details of the concepts and results presented can be found.

Last changes: July 20, 2011