TUM – TUM – Menü

Polyhedral Combinatorics (MA5225)
Vorlesung

Lecturer: Prof. Dr. P. Gritzmann
Tutorials: Maximilian Fiedler
Weekly hours: 3+1 hours
ECTS credits: 6

After successful completion of the module, the students will be familiar with a general most powerful state-of-the-art paradigm for solving NP-hard combinatorial optimization problems. They will understand the link between the geometry and combinatorics of polytopes and the optimization of linear functionals over them. They will be able to apply the derived algorithms to challenging problems. Also they will be aware of the limitations in fire of NP-hardness. Topics covered among others are representations of polytopes, running time of the simplex algorithm, diameter of polytopes, branch-and-cut algorithms, separation and optimization, facial description of basic polytopes in combinatorial optimization (e.g. matching polytope, TSP-polytope etc.) and extended formulations.

News Schedule Lecture Exercise Sheets Exam Literature

News

  • 12.10.17: The first lecture will take place on Tuesday 17th of October from 14:00 to 16:00, the second on Wednesday the 18th of October at 10:15.
  • 12.10.17: The registration for the tutorials is open.

Schedule

  Day Time Room Lecturer Dates
Lecture Tuesday 14:00 - 16:00 Seminarraum (M9/M10) Prof. Dr. P. Gritzmann weekly
Lecture Wednesday 10:15 - 11:45 MI HS 3 Prof. Dr. P. Gritzmann 18.10, 15.11, 29.11, 13.12, 10.01, 24.01

Tutorial Day Time Room Lecturer Dates
Group 01 Wednesday 12:00 - 14:00 MI 00.08.055 Maximilian Fiedler biweekly

Lecture

Lecture Date
01 17.10
02 18.10
03 24.10
04 07.11
05 14.11
06 15.11
07 21.11
08 28.11
09 29.11
10 05.12
11 12.12
12 13.12
13 19.12
14 09.01
15 10.01
16 16.01

Exercise Sheets

  • There will be an exercise sheet every two weeks, that will be discussed in the tutorials.
  • Please print the exercise sheets at home and bring them with you.
  • In order to make the best of the tutorials' time, have a look at the exercises in advance.
  • All sheets will be password protected. The login details will be announced in the lecture.

Exercise Sheet Suggested Solution Remarks
01 01  
02 02  
03 03  
04 04  
05 05  
06    

Exam

Important Information

  • Depending on the number of course participants the exam will be either oral or written
  • All topics covered in the lecture and the exercises are relevant for the exam.
  • Registration via TUMOnline is mandatory for participation in the exam (registration for the lecture and/or the exercise classes is not sufficient)! Please do not forget to register until that date - you will not be allowed to take the exam without prior registration on TUMOnline.
  • In case you have been granted any special regulations for your examination, please make sure to inform us via mail during the registration period. Failure to notify us by that time means you voluntarily forfeit your right to any special regulations for that exam.
  • Please turn off mobile phones, tablets, notebooks, calculators etc. and store them in your bag. Handling any kind of electronic equipment, whether switched on or not, will be considered an attempt at cheating. Of course, the same goes for lecture notes, books, etc.
  • Please make sure to be in the examination room at least 10 minutes prior to the scheduled starting time.
  • Bring a photo ID (passport or drivers license) and your student ID. We will check the IDs during the exam.
  • The grades will be published in TUMOnline only.

Literature

  • B. Korte, J. Vygen: Combinatorial Optimization, Springer, 2002
  • A. Schrijver, Combinatorial Optimization, Springer 2003
  • M. Grötschel, L. Lovasz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer 1988
  • Gritzmann: Grundlagen der Mathematischen Optimierung, Springer, 2013
  • various journal publications and preprints

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

News

March 2017
February 2017
Case Studies 2017 registration deadline: March 5th, 2017
January 2017
Case Studies 2017 pre-meeting and registration information
January 2017
preliminary Summer 2017 course program is available