Approximation Algorithms, 6 points, period 1-2, 10/11

The goal of the course is to learn the underlying techniques used when designing approximation algorithms, by study famous applications from the literature. Starting with basic techniques such as "greedy algorithms" and then moving on to more powerful paradigms including the use and analysis of linear/semidefinite programs. The exact topics to be covered will depend on our interests and any suggestions are very welcomed. For inspiration I have prepared a list of possible topics that I find interesting (see here).


Thanks for a great course that I have really enjoyed teaching. A summary of the course evaluations is available here .

Sixth and final set of homeworks due December 21 is available, see below.


Ola Svensson, is responsible for all aspects of this course. Tobias Mömke, helped out by giving 1.5 lectures and homework 5 on iterative rounding. Cenny Wenner and Lukas Polacek helped out by giving one lecture each on Semidefinite programming and homework 6. Lectures will be given in English.

Course requirements

Course requirements are given by biweekly assignments. Students may also choose to complement (or replace) some of the assignments with a project work.

Students that are interested in doing a project should first discuss the topic with me (Ola)!

Course material

The material of the course will be articles, notes, and parts of the book "Approximation Algorithms" by V. Vazirani. The book is also available on the web as a pdf .


First set of problems which is due October 12.

Second set of problems which is due October 26.

Third set of problems which is due November 9 (changed to 16).

Fourth set of problems which is due November 23.

Fifth set of problems which is due December 7.

Sixth set of problems which is due December 21.

Schedule and References

The plan of topics is preliminary and will probably change. However, I will aim towards keeping the topics of the next two lectures up to date.

 Presentation of Course Tuesday 15-17 September 21 1537  Slides pptx 8MB ( pdf 12MB and buggy)
 Greedy Algorithms Tuesday 13-15 Sep 28 1537 Sections 2.1 and 10.1 in the book.
 Local Ratio Tuesday 13-15 Oct 5 1537  Survey, Feedback Vertex Set, Demos during lecture
 Approximation to Any Degree Tuesday 13-15 Oct 12 4523 Chapters 8 and 10 in Vazirani's book. See also dynamic program examples (pptx).
 LP intro Tuesday 13-15 Oct 19 4523  Chapters 10,12 and Section 14.3 in Vazirani's Book. Slides PTAS LP Intro
 LP using extreme point structure Tuesday 10-12 October 26 1537 Chapters 14 and 17 in Vazirani's book
 LP Using extreme point and intro to duality Tuesday 10-12 November 2 304 "22:an" Ringen huset Chapters 13 and 17 in Vazirani's book
 LP Primal-Dual Tuesday 10-12 November 9 4523 Chapter 15 and perhaps 24 in Vazirani's book
 Primal-Dual and intro to LP Iterative Rounding Tuesday 10-12 November 16 304 "22:an" Ringen huset Chapter 24 in Vazirani's book see also lecture notes and the powerpoint demos
 LP Iterative Rounding Tuesday 10-12 November 23 1537 pages 12-19, 30-37 of the book draft
 Semidefinite Programming Tuesday 10-12 November 30 1537 Chapter 26 in Vazirani's book
 Semidefinite Programming Tuesday 10-12 December 7 1537 See paper
 Hardness of Approximation Wednesday 13-15 December 15 4523 Chapter 29 in Vazirani's book


Similar courses given previously at other universities:
Sidansvarig: <>
Senast ändrad 1 September 2010
Tekniskt stöd: <>