Combinatorial Optimisation
Lecturer:
Leen Stougie, Vrije Universiteit Amsterdam & CWI
Email: l.stougie@vu.nl
Organization
The lectures will be on Tuesdays and Thursdays. The exercises will be discussed usually on Thursdays.
Tuesday: 
15:3017:15, room HG04A04 
Thursday: 
15:3017:15, room HG04A04 
The lectures start on February 7, 2013.
Course materials
The course is covered by parts of the following two books:

C. H. Papadimtriou and K. Steiglitz, Combinatorial Optimization, PrenticeHall, 1982.

D.P. Williamson and D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2010.
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 PrenticeHall.) The book [WS] will also be used in the course Caput OR (Advanced Algorithms).
Examination
The examination consists of a written exam and a written reexam. See for the correct working out of the exam of March 25, 2013, below.
The examination is a semiopen 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 workingout. Notice that this exam is not very representative for the exam of 250312. 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 workingout. This exam is representative for the exam on 25 March 2013.
The workingout 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.

07022012: Basics of Graph Theory: Apart from learning some basic graph theory, this part is also meant to teach you the art of theorem proving in a combinatorial setting.

Reading: The lecture notes on Basics of Graph Theory and Ford Fulkerson's algorithm for maxflow, including the maxflow mincut theorem, Chapter 6, Sections 1,2.}

It is required that each of the students studies the lecture notes on the basics of Graph Theory by Alexander Schrijver Grafen: Kleuren en Routeren. During the rest of the course all definitions but also proof techniques are supposed to be known. An excerpt of these lecture notes and translated into English is found in Basics of Graph Theory.
The lecture notes on Flows I made for myself for teaching. An example of how the FordFulkerson augmenting path algorithm works you find in my ExampleFFalgorithm PowerPoint presentation.

Exercises: The exercises are found in the lecture notes. There are 107 of them, most of them very easy. The flow exercises are found in the lecture notes.

Answers to the Exercises on Graph Theory: The
workouts of some exercises of Schrijver's lecture notes, and a growing list of answers to others from the same lecture notes.

12022013: Running time analysis of algorithms. An efficient algorithm for Maxflow.

Reading: [PS]: Chapter 6, Section 6.3; Chapter 8, Sections 8.1  8.5; Chapter 9, Sections 9.1  9.4; Chapter 12: Sections 12.1  12.3.

The lecture notes on Flows I made for myself for teaching. An example of how the FordFulkerson augmenting path algorithm works you find in my ExampleFFalgorithm PowerPoint presentation.

Exercises: The exercises are found in the lecture notes.

14022013 and 19022012: Matchings

Reading: [PS]: Chapter 10: Sections 10.110.3, Section 10.4 (just read the
difficulties with finding augmenting paths because of blossoms; Chapter 11: Sections 11.1 and 11.2 and Chapter 7: Section 7.4
(In Chapter 11 the book gives only a very partial description
of the Hungarian Method. The exact description of the algorithm for the more general
Hitchcock Problem is found in Chapter 7, Section 7.4); Chapter 13: Section 13.2 (Total Unimodularity)

The lecture notes on
Matchings I made for myself for teaching. An example of an augmenting path iteration for bipartite matching you find in my
ExampleBMalgorithm PowerPoint presentation.

Exercises: The exercises are found in the lecture notes.

Answers to the Exercises on Matching: The
answers to exercises of Chapters 10 and 11.

21022013, 26022013 and 28022013: Complexity Theory

Reading: [PS]: Chapter 8 (excl. Sec. 8.6, 8.7) You may like to read 8.6 that shows that Simplex is not an efficient algorithm for LP ; Chapter 15 (excl. Sec. 15.5, which courageous students may try to understand ); Chapter 16 (excl. Sec. 16.3, 16.4)

Lecture notes on Complexity Theory.

Exercises: The exercises are found in the lecture notes.

Answers to Exercises on Complexity Theory: The
answers to exercises in the Lecture Notes and some to Exercises in [PS] .

05032013 and 07032013: Approximation Algorithms

12032013 and 14032013: Algorithmic Game Theory by Guido Schaefer

19032013: 15:30u17:15u; Room 4A04 (as usual) Instruction on Exam Exercises
This page has been made by Leen Stougie, and updated last on March 18, 2013.