MPII Home PageMPII Home PageMPII Home Page
AG1 : Teaching
 Vorlesungsverzeichnis der AG1 Building 46.1


To register please send EMail to E. Althaus or F. Eisenbrand

Seminar on ``Integer Programming and Combinatorial Optimization'' - WS 2003/2004


Instructors

Dr. Friedrich Eisenbrand

Building 46 (MPII), Room 428
Dr. Ernst Althaus
Building 46 (MPII), Room 304

Time and place


First, preparatory meeting :
Tu, Oct. 21th. 2pm, rotunda 4th floor, MPI
First meeting in the Semester:
 We, Oct. 29th 13.30-15.00, Room 023, MPI
Last meeting in the Semester: We, Feb. 11th

Topics

DateTopicSpeakerAdvisorReference
Oct. 29A short proof for strong duality FritzErnst
Nov. 5Formulating and solving problems via integer programming ErnstFritz A tutorial on integer programming
Nov. 12 Cutting planes, Gomory Mixed-Integer, general cutting planes Gennady ShmoninFritz Laurence Wolsey, Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization
Nov. 19 Minimum cut, Gomory-Hu trees Lijun ZhangFritz B. Korte and J. Vygen, Combinatorial Optimization, Springer
Nov. 26 Lagrangean duality Junming YinErnst Laurence Wolsey, Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization
Dec. 10 The Matching Polytope Deepak AjwaniFritz B. Korte and J. Vygen, Combinatorial Optimization, Springer
Dec. 17 The Knapsack Problem Christian GrossFritz
Jan. 7 Multicommodity Flows Imran RaufErnst B. Korte and J. Vygen, Combinatorial Optimization, Springer
Jan. 14 No talk!
Jan. 21 Jain's Algorithm Adrian AlexaErnst B. Korte and J. Vygen, Combinatorial Optimization, Springer
Jan. 28 Approximation algorithm for the TSP in the plane Dominik SchultesErnst V.J. Vazirani, Approximation Algorithms, Springer
Feb. 4 Lattice basis reduction - LLL algorithm Muhammad Kamran AzamErnst V.J. Vazirani, Approximation Algorithms, Springer
Feb. 11 Matroid Polytope and Matroid Intersection Evghenia StegantovaErnst Korte and J. Vygen, Combinatorial Optimization, Springer
Feb. 18 Matching in general graphs Januzaj VisarErnst B. Korte and J. Vygen, Combinatorial Optimization, Springer

About the seminar

  • This is a 9 points (9 LP) seminar.
  • Everybody is expected to give a very well accessible presentation of the topic assigned to him/her
  • Talk has to be presented with the help of slides, ideas of proofs have to be given on the black board
  • One week before the talk, the candidate has to present his talk, together with Latexed summary to his advisor
  • Grades are assigned according to the talk (70%) and to the written summary of the topic (30%).