Combinatorial Optimisation

Leen Stougie, Vrije Universiteit Amsterdam & CWI


The lectures will be on Tuesdays and Thursdays. The exercises will be discussed usually on Thursdays.

Tuesday: 15:30-17:15, room HG-04A04
Thursday: 15:30-17:15, room HG-04A04

The lectures start on February 7, 2013.

Course materials

The course is covered by parts of the following two books:

We use [PS] and [WS], respectively, to refer to these books.

Note: Most relevant parts of these books can also be found online. Here are the respective links to the online versions: [PS] and [WS]. (Note that the [PS] link refers to the Dover edition of the book (published in 1998) which is a corrected, unabridged republication of the original work published in 1982 by Prentice-Hall.) The book [WS] will also be used in the course Caput OR (Advanced Algorithms).


The examination consists of a written exam and a written re-exam. See for the correct working out of the exam of March 25, 2013, below.

The examination is a semi-open book exam: the only thing allowed to bring to the examination is the book Combinatorial Optimization by Papadimtriou and Steiglitz listed above, not containing any separate leaflets.

All electronic devices have to be switched off during the examination.

Please find here the exam of 21 March 2011, and the version including correct answers.

Below find some exams of the Master's course, which was given until two years ago. The level of the exercises will be the same, but some of the subjects may not be covered in this course.

The exam of 20 October 2009 and a correct working-out. Notice that this exam is not very representative for the exam of 25-03-12. Specifically, exercises like 1 and 3 of the exam are highly unexpected to return in a future exam. The exercises 2,4 and 5 are representative.
The exam of 29 March 2012 and a correct working-out. This exam is representative for the exam on 25 March 2013.
The working-out of the exam on 25 March 2013.

Course content

A plan of the course is given below and has been updated weekly.

Your comments on presentation and lecture notes (see below) are highly appreciated. Also please point me to any disturbing typing errors in the lecture notes.

I assume that everyone knows the material covered in [PS] Chapters 1,2,3,4 and 5, except for Section 4.4.

This page has been made by Leen Stougie, and updated last on March 18, 2013.