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.
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)!
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.
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 |