Combinatorial Optimisation

Lecturer:
Leen Stougie, Vrije Universiteit Amsterdam & CWI
E-mail: l.stougie@vu.nl

Organization

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

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, Prentice-Hall, 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 Prentice-Hall.) 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 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.

• 07-02-2012: 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 max-flow, including the max-flow min-cut 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 Ford-Fulkerson augmenting path algorithm works you find in my ExampleFFalgorithm Power-Point 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.
• 12-02-2013: Running time analysis of algorithms. An efficient algorithm for Max-flow.
• 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 Ford-Fulkerson augmenting path algorithm works you find in my ExampleFFalgorithm Power-Point presentation.
• Exercises: The exercises are found in the lecture notes.
• 14-02-2013 and 19-02-2012: Matchings
• Reading: [PS]: Chapter 10: Sections 10.1-10.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 Power-Point 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.

• 21-02-2013, 26-02-2013 and 28-02-2013: 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] .

• 05-03-2013 and 07-03-2013: Approximation Algorithms
• Reading: [PS] Chapter 17; [Vaz]: Chapter 16, here is a scan of the chapter.
• Lecture notes on Approximation Algorithms.
• Part of the material can also be read in [Vaz], Chapter 3.2; Chapter 8; Chapter 10 (only 10.1).
• Exercises: The exercises are found in the lecture notes.
• Answers to Exercises on Approximation Algorithms: The answers to exercises in the Lecture Notes and some to Exercises in [PS] and [Vaz] .

• 12-03-2013 and 14-03-2013: Algorithmic Game Theory by Guido Schaefer
• Reading: Lecture notes by Guido Schaefer on Algorithmic Game Theory. Also find here upon request of the students a copy of his slides

• 19-03-2013: 15:30u-17:15u; Room 4A-04 (as usual) Instruction on Exam Exercises