|
Polyhedral Combinatorics
(ADM III) |
|
| |
Summer Term 2010 |
|
LV-Nr.: 3236 L 414
This lecture will be offered by the Berlin Mathematical School in English language.
Polyhedral combinatorics can be viewed as a technique that uses methods from polyhedral theory and linear algebra in order to solve combinatorial problems.
The main idea is to transform a combinatorial problem into a polyhedral problem by, for instance, considering the convex hull of the incidence vectors of the feasible solutions
of the combinatorial problem, and to employ techniques from linear and integer programming in order to solve the combinatorial problem. At the end of this class the students will be able to handle this methodology, apply it to practically relevant cases,
and prove important results. The focus will be on the solution of NP-hard combinatorial optimization problems.
First lecture of ADM III "Polyhedral Combinatorics" took place on 13. April 2010, 16:00-18:00 h, at TU Berlin, room MA 041.
There aren't lecture notes, but I prepared a summary with a detailed review and bibliographical references. I will complete this material continuously.
Important combinatorial problems that will be addressed include the travelling salesman, the max-cut, the linear ordering,
the stable set (including perfect graphs and the theta-body), and the matching problem. We will, for example, study the facet structure of the polytopes associated
with these problems and show how to employ cutting plane techniques for the solution of these optimization problems.
Instances from real-world will illustrate the range of problems that come up and can be solved in practice.
mandatory: Linear and Integer Optimization (ADM II)
preferable: Linear Algebra, Graph and Network Algorithms (ADM I)
| Lecture: |
| Tuesdays |
16:15 - 17:45 h |
room MA 041 |
| There are no exercises! |
Contacts
| |
|
Sprechstunde
|
Room |
Phone |
Email |
| Office at TU |
Martin Grötschel |
n.V. |
MA 302 |
314-23266 |
groetschel zib.de (ZIB) |
| Office at ZIB |
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 |
- 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
We do not publish lecture notes, but I prepared a summary with a detailed review and bibliographical references. I will complete this material continuously.
In summer term 2010 I also offer a Project Seminar: Discrete Optimization.
last changed: May 20, 2010
Content