Approximation Algorithms
5
Algoritmit ja koneoppiminen
Syventävät opinnot
Design techniques of approximation algorithms: greedy algorithms and local search, rounding data and dynamic programming, linear programming relaxations. Example problems: Vertex Cover, Set Cover, Metric Steiner Tree and TSP, Knapsack, Bin Packing. (A larger course with the same name was given in 2010.) Prerequisites: the course Design and Analysis of Algorithms or equivalent. Course book: D. P. Williamson, D. B. Shmoys: The design of Approximation Algorithms, Cambridge University Press, 2011.
Koe
03.03.2015
16.00
A111
| Vuosi | Lukukausi | Päivämäärä | Periodi | Kieli | Vastuuhenkilö |
|---|---|---|---|---|---|
| 2015 | kevät | 14.01-27.02. | 3-3 | Englanti | Mikko Koivisto |
Luennot
| Aika | Huone | Luennoija | Päivämäärä |
|---|---|---|---|
| Ke 12-14 | B222 | Mikko Koivisto | 14.01.2015-27.02.2015 |
| Pe 12-14 | B222 | Mikko Koivisto | 14.01.2015-27.02.2015 |
Information for international students
The course will be given in English, unless all attenting students can speak Finnish.
Yleistä
For many practically and theoretically important computational problems, we do not know any efficient algorithm that would always output the correct solution sufficiently fast. Approximation algorithms offer one approach to cope with such problems. Approximation algorithms generally refer to algorithms whose output is more or less close to the exact, correct solution.
Approximation Algorithms is an elective, advanced-level course in computer science. The course teaches basic concepts in the field of approximation algorithms, particularly a set of design principles and paradigms with applications to a collection of prototypic algorithmic problems. The course focuses on polynomial-time approximation algorithms to optimization problems. The treatment emphasizes provable guarantees regarding both the running time and the approximation accuracy of an algorithm, thus taking a theoretical rather than practical viewpoint. Two important topics that the course does not cover are approximation algorithms for counting problems (especially MCMC) and advanced tools for showing approximation hardness (especially the PCP theorem).
Learning objectives:
- describes several known results of approximation algorithms, including a few inapproximability results;
- applies basic design principles to simple problems;
- proves approximation guarantees for algorithms derived using basic design principles;
- proves inapproximability (assuming P is not NP) results using simple polynomial-time reductions.
Kurssin suorittaminen
NEW: PLEASE GIVE FEEDBACK USING THE FORM YOU CAN FIND HERE. DO IT, E.G., AFTER THE COURSE EXAM.
NEW: Course exam was held on March 3. See the questions and model solutions. Grading is now complete for those who attended the course exam. The grade distribution: 1, 2****, 3, 4*, 5*. The threshold points for the grades were 22, 28, 34, 40, 46. These were lowered by 2 points from the default thresholds, as the first question appeared to be surprisingly hard to many. (Many got 0 points! Nobody got negative total points, for the lower bound of zero was in use. You should not guess unless you are pretty sure about the correct answer! Note also that the first question was not just about memorizing the theorems but also about being able to reason about different approximation qualities. And, if one remembers something about the proof behind a theorem, then memorizing the statement is not that difficult; consider, e.g., TSP versus Metric TSP.)
Note: Every participant of the course is welcome to take the renewal exam on April 17.
The minimum requirement for passing the course is to earn a sufficient amount of points, tentatively 24. The maximum number of points is 60, which consists of exam points and exercise points as follows:
- Exercises: max 12 points. (Can be earned only during the period of the lecture course.)
- Course exam: max 48 points. (Controlled 2.5 hours. Can be taked only during the period of the lecture course.)
- Renewal exam: max 48 points. (Controlled 3.5 hours. Can be taken just after the period of the lecture course.)
- Separate exam: max 60 points. Exercise points not counted. (Controlled 3.5 hours.)
You are allowed to bring one paper sheet (A4 size) to the exam, but no calculator, phone, etc.
Exercises: The course book contains a good number of exercise problems. Solving some of the problems constitutes the major part of the work during the course. For each week, the lecturer selects a set of exercise problems and divides them into two categories:
- Graded exercises: typically 3 problems. Students are supposed to solve the problems individually and submit written solutions to the lecturer by the given deadline. The solutions are graded as 0 (not solved, partially solved but poorly presented), 1 (partially solved or very good attempt, solved but poorly presented), 2 (solved and well presented). The grades contribute linearly to the exercise points. The graded solutions are returned back to the student, possibly including also verbal feedback on selected solutions.
- Ungraded exercises: the number and difficulty of problems may vary a lot. The solutions do not contribute to exercise points. The purpose of the ungraded exercises is to train some very basic things, deepen understanding, or just provide additional material for training and testing.
Example solutions will be made available on the course web page at least for all graded problems.
Lectures: Because we follow the course book very closely, traditional lecturing is kept at minimum. The lectures are rather meetings where questions are asked and answered, ungraded exercise problems are solved together, and solutions to graded exercises are discussed (a fixed lecture hour in each week).
Kirjallisuus ja materiaali
Course book (WS): D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011. See the website for downloading a free pdf copy.
Martin Skutella's slides offer a nice summary of each chapter of the course book.
See also the Wikipedia page for a short introduction to approximation algorithms and pointers to other relevant literature.
An elegant survey of the primal-dual method by Michel Goemans and David Williamson.
Content and schedule: The seven lecture weeks will cover selected parts the first seven chapters of the course book in the logical order, one chapter per week; however, we will skip Chapter 6 (Randomized rounding of semidefinite programs) and instead use the last week for extra discussion and exercises. The following sections are treated as extra material not covered in the course: 2.6-7, 5.10-12, and 7.7.
Before the first lecture hour each week, it is recommended to do the following:
- Read the chapter in question in the course book.
- Submit your solutions to the graded exercises (G-exercises) given in the previous week, to the lecturer either by email or in paper. Hints and solutions to graded exercises.
Week I: An Introduction to Approximation Algorithms (Chapter 1 of WS).
G-exercises: 1.1(a), 1.1(b), 1.4(a-b), due Wed 21 Jan 12:15am, discussion Fri 23 Jan 13:15pm. .
Week II: Greedy Algorithms and Local Search (Chapter 2 of WS).
G-exercises: 2.1(b), 2.3, 2.10, due Wed 28 Jan 12:15am, discussion Fri 6 Feb 12:15pm.
Week III: Rounding Data and Dynamic Programming (Chapter 3 of WS). Note: no meeting on Friday 30th January.
G-exercises: 3.1, 3.2, 3.6, due Wed 4 Feb 12:15am, discussion Fri 6 Feb 13:15pm.
Week IV: Deterministic Rounding of Linear Programs (Chapter 4 of WS).
G-exercises: 4.1, 4.7(a-b), 4.7(c-e), due Wed 11 Feb 9:15am, discussion Wed 11 Feb 12:15pm.
Week V: Random Sampling and Randomized Rounding of Linear Programs (Chapter 5 of WS). U-exercises 5.3, 5.4.
G-exercises: 5.6(a), 5.6(b), 5.8 (worth 2, 2, 3 points, respectively), due Wed 18 Feb 9:15am, discussion Wed 18 Feb 12:15pm.
Week VI: The Primal-Dual Method (Chapter 7 of WS).
G-exercises: 7.1 and 7.8 (worth 3 and 2 points, respectively), due Wed 25 Feb 9:15am, discussion Wed 25 Feb 12:15pm.
Week VII: Summary.