Combinatorial Optimization WS 04/05

News:

28.10.04	Literature for the course is now specified on the web page
22.10.04	Due to construction work, the lecture on Monday, Oct 25th, takes place in room 023
21.10.04	Due to construction work, the lecture on Friday, Oct 22nd, takes place in room 023
21.10.04	A mailing list for this lecture has been set up. Please subscribe to this list if you participate in the lecture

Lecturer:

PD Dr. Friedrich Eisenbrand

Contents:

This course will be held as an in-depth lecture to the subject of 'Algorithms and Complexity'. It is a follow-up class to the basic lecture 'Optimization' in theoretical computer science. We will focus on integer linear programming and associated techniques. Especially, we will deal with the special case of 0/1 optimization problems. Cohesively, we will set up a programming project to improve your understanding of the matter. For this mandatory practical exercise, we will provide a framework such that no extraordinary programming skills are required to succeed.

Dates:

Language:

The lecture will be held in english or in german depending on the audience.

Grading:

The credit for this course is 9 graded Leistungspunkte, i.e. there will be four hours of lectures and an exercise session every week. The credit is awarded upon successful participation at the final exam. The course grade is only determined by the grade of the final exam. Successful participation in the exercises (theoretical and practical) are necessary to be admitted to the final exam.

Literature:

Korte, Bernhard and Vygen, Jens: Combinatorial Optimization - Theory and Algorithms; Second Edition.
Algorithms and Combinatorics. Springer, Berlin;Heidelberg;New York (2002).

Schrijver, Alexander: Theory of linear and integer programming.
Wiley-Interscience series in discrete mathematics and optimization. reprinted 1999 edition. Wiley, Chichester (1986).

Nemhauser, Georg L. and Wolsey, Laurence A.: Integer and combinatorial optimization.
Wiley, Chichester (1988).

Assignments:

Assignment 1, due Friday Oct 28th	ps	pdf
Assignment 2, due Monday Nov 8th	ps	pdf
Practical Assignment 1, due Tuesday Nov 23rd	ps	pdf
Assignment 3, due Monday Nov 22nd	ps	pdf
Assignment 4, due Monday Nov 29th	ps	pdf
Assignment 5, due Monday Dec 6th	ps	pdf
Assignment 6, due Monday Dec 13th	ps	pdf
Assignment 7, due Monday Dec 20th	ps	pdf
Practical Assignment 2, due Monday Jan 10th	ps	pdf
Assignment 8, due Monday Jan 17th	ps	pdf
Assignment 9, due Monday Jan 24th	ps	pdf
Practical Assignment 3, due Monday Feb 7th	ps	pdf
Assignment 10, due Friday Feb 11th	ps	pdf