Caput OR 4.1: Advanced Algorithms (Fall 2011)

 

Announcements:

  1. •Dec 20, 2011: Solutions to the re-exam on December 16, 2011 are online.

  2. •Dec 7, 2011: The written re-exam is on Friday, December 16, 2011, 11:45-15:00, in room HG-04A04. Lecture Notes, books, etc. are not allowed during the exam. Just pen and paper.

  3. •Dec 7, 2011: Some additional notes on the PTAS for the TSP problem are available online: Chapter 11 of Vazirani is the material for this subject. These notes maybe help you to understand more details.

  4. •Nov 11, 2011: Solutions to the exam on October 28, 2011 are online.

  5. •Oct 25, 2011: The written exam will take place on Friday, October 28, 2011, 12:00-14:45 in HG-05A02. Lecture Notes, books, etc. are not allowed during the exam. Just pen and paper.

  6. •Oct 20, 2011: Assignment results are online.

  7. •Oct 20, 2011: Lecture notes of weeks 9 & 10 (by Felix) are available online.

  8. •Oct 20, 2011: Solutions to Assignment 3 are online.

  9. •Oct 14, 2011: Lecture notes of weeks 7 & 8 (by Vincent) are available online.

  10. •Oct 6, 2011: Assignment 3 has been issued and is due on Oct. 13.

  11. •Oct 6, 2011: Corrections of Assignment 2 were given back.

  12. •Sep 30, 2011: Solutions to Assignment 2 are online.

  13. •Sep 23, 2011: Rene will take over classes next week.

  14. •Sep 23, 2011: Lecture notes (Guido’s part) are finalized.

  15. •Sep 23, 2011: Corrections of Assignment 1 were given back yesterday.

  16. •Sep 22, 2011: Assignment 2 has been issued and is due on Sep. 29.

  17. •Sep 16, 2011: Solutions to Assignment 1 are online.

  18. •Sep 8, 2011: Assignment 1 has been issued and is due on Sep. 15.

  19. •Sep 7, 2011: Lecture notes and additional material are available online (see “Course Material” below).

  20. •Aug 16, 2011: Course starts on Wednesday, September 7, 2011: 13:30-15:15, room HG-11A02.


Course Description:

In this course we will learn how to develop efficient algorithms for solving fundamental optimization problems with applications in routing, network design and scheduling. The objectives of the course are:

  1. •get to know fundamental optimization problems that are computationally hard to solve if we insist on exact methods

  2. •learn how to efficiently find good solutions to these problems (despite their computational intractability)

  3. •study basic and advanced techniques to approach such problems; techniques that will most likely be covered in class are: greedy method, dynamic programming, randomized and iterative rounding, dual fitting, primal-dual schema, etc.

  4. •learn to use these techniques in order to design approximation algorithms.


The following optimization problems will be covered in the lecture: vertex cover, set cover, knapsack, facility location, traveling salesman, Steiner tree, Steiner network, scheduling, ...


The course is part of the Master's programme in Econometrics and Operations Research at the VU University Amsterdam and accounts for 6 credit points. Besides the material that we cover in class, we will also ask you to study some material on your own and to solve three take-home assignments. You might get a bonus point for the final grade if you solve most of the problems of the assignments correctly (see below for details).


Credit points: 6

ISIS code: E_EORM_COR


Prerequisites:

Basic knowledge on algorithms and computational complexity is advantageous (see, e.g., material covered in the bachelor course Combinatorial Optimization); see “Course Material” below for a more detailed reading advise.


Time and Location:

The course consists of 12 lectures (2h each) and takes place Wednesdays and Thursdays. The lectures start on Wednesday, September 7, 2011 and end on Thursday, October 13, 2011.


Wednesdays:     13:30-15:15, HG-11A02

Thursdays:         15:30-17:15, HG-08A04


The course is split into two parts: The lectures of the first three weeks will be given by Guido. After that, Rene will take over.


Lecturers:

  1. •Prof. Dr. Guido Schäfer
    Email: g dot schaefer at cwi dot nl
    Room: HG-01E61 (office hours by appointment)

  2. •Dr. Rene Sitters
    Email: r.a.sitters at vu.nl


Assessment:

Written exam on Friday, October 28, 2011, 12:00-14:45, HG-05A02. The re-exam is on Friday, December 16, 2011, 11:45-15:00, in room HG-04A04. Lecture Notes, books, etc. are not allowed during the exam. Just pen and paper.


Assignments:

We will issue three take-home assignments on a bi-weekly basis. The assignments have to be handed in the week after (Thursdays, during the lecture). You may get a bonus point on top of your final grade of the exam if you solve 66% of the problems given in the take-home assignments correctly. You can work out the assignments either on your own or in groups of two.

  1. •Assignment 1 (issued Sep. 8), due Sep. 15. Solutions.

  2. •Assignment 2 (issued Sep. 22), due Sep. 29. Solutions

  3. •Assignment 3 (issued Oct. 6), due Oct. 13. Solutions


References and Links:

The main text book of the course is the following one:

  1. •[Vaz01]: V. V. Vazirani, Approximation Algorithms, Springer, 2001.


A more recent text book containing a lot of material on approximation algorithms is the following one (electronic-only version available online):

  1. •[WS11]: D. P. Williamson and D. Shmoys, The Design of Approximation Algorithms, Cambridge University Press. Electronic-online version available here.


Supplementary material can be found in

  1. •[KT05]: J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005.

  2. •[PS82]: C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization; Algorithms and Complexity, Prentice-Hall, 1982.


Course Material:


Prerequisites:

  1. •You should have some basic knowledge of algorithms for fundamental optimization problems (e.g., minimum spanning tree, matching, shortest path, max flow) and their running time analysis (e.g., polynomial vs. exponential running time, O-notation). If you are not familiar with these topics, the lecture notes of last years’ bachelor course on Combinatorial Optimization might be a good start to get the necessary background information.

  2. •If you are not familiar with Complexity Theory, then we recommend that you study the Lecture Notes: Complexity Theory of last year’s bachelor course on Combinatorial Optimization to get some deeper insights into the topic. You do not need to understand every single detail but should try to get an overall understanding of what P vs. NP is about.


Lecture Notes of the first part of the course (Guido’s part).


Additional online material can be found here.


Guido’s part:


Lecture 1:

  1. •Topics: Introduction, definition of approximation algorithms, 2-approximation for vertex cover

  2. •Background reading: Chapter 1 (excl. Sections 1.2 and 1.3) of [Vaz01]

  3. •Homework: Read-up to meet the Prerequisites outlined above.


Lecture 2:

  1. •Topics: Greedy algorithm for set cover, dynamic program for knapsack

  2. •Background reading: Chapter 2 (excl. Sections 2.2 and 2.3) & 8 (excl. Section 8.3) of [Vaz01]

  3. •Assignment 1 has been issued and is due on Sep. 15

  4. •Homework: Read-up to meet the Prerequisites outlined above and study Chapter 12 of [Vaz01] as preparation for next week.


Lecture 3:

  1. •Topics: Approximation scheme for knapsack, prerequisites LP techniques

  2. •Background reading: Chapters 8 (excl. Section 8.3) & 12 of [Vaz01]

  3. •Homework: Study Chapters 13 (excl. Section 13.2) & 15 of [Vaz01]


Lecture 4:

  1. •Topics: dual fitting, primal-dual scheme, set cover revisited

  2. •Background reading: Chapters 12, 13 (excl. Section 13.2) & 15 of [Vaz01]

  3. •Homework: Study Chapter 14 (excl. Sections 14.2 and 14.3) of [Vaz01] by yourself.


Lecture 5:

  1. •Topics: primal dual scheme, Steiner forest

  2. •Background reading: Chapter 22 of [Vaz01]


Lecture 6:

  1. •Topics: Steiner forest (continued), discussion

  2. •Background reading: Chapter 22 of [Vaz01]

  3. •Assignment 2 has been issued and is due on Sep. 29


Rene’s part:


Lecture 7:

  1. •Topics: Euclidean traveling salesman problem

  2. •Background reading: Chapter 11 of [Vaz01]; paper by Arora

  3. •These notes maybe help you to understand more details.


Lecture 8:

  1. •Topics: Euclidean traveling salesman problem (continued)

  2. •Background reading: Chapter 11 of [Vaz01]; paper by Arora

  3. •These notes maybe help you to understand more details.


Lecture 9:

  1. •Topics: Maximum Satisfiability

  2. •Background reading: Chapter 16 of [Vaz01]


Lecture 10:

  1. •Topics: Semidefinite Programming

  2. •Background reading: Chapter 26 of [Vaz01]

  3. •Assignment 3 has been issued and is due on Oct. 13.


Lecture 11:

  1. •Topics: Scheduling on unrelated machines

  2. •Background reading: Chapter 17 of [Vaz01]


Lecture 12:

  1. •Topics: Hardness of approximation

  2. •Background reading: Chapter 29-1 of [Vaz01] (only Section 1)