Approximation Algorithms

582456
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

07.03.2017 16.00 B123
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2017 kevät 17.01-03.03. 3-3 Englanti Mikko Koivisto

Luennot

Aika Huone Luennoija Päivämäärä
Ti 12-14 C222 Mikko Koivisto 17.01.2017-28.02.2017
Pe 12-14 C222 Mikko Koivisto 20.01.2017-03.03.2017

Information for international students

The course will be given in English, unless all attending students 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.

The course exam will be held on March 7 at 16:00 in B123.

The renewal/separate exam will be held on April 21 at 16:00 in B123. Note: take the exam and the points will be counted (as in a renewal or separate exam) in the way that is the best for you.

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 (homework): 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 (classwork): 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:

1. Read the chapter in question in the course book.
2. 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 Tue 24 Jan 12:15pm, discussion Fri 27 Jan 13:15pm.

Week II: Greedy Algorithms and Local Search (Chapter 2 of WS).
G-exercises: 2.1(b)2.32.10due Tue 31 Jan 12:15pm, discussion Fri 3 Feb 13:15pm.

Week III: Rounding Data and Dynamic Programming (Chapter 3 of WS).
G-exercises: 3.13.23.6due Tue 7 Feb 12:15pm, discussion Fri 10 Feb 13:15pm.

Week IV: Deterministic Rounding of Linear Programs (Chapter 4 of WS).
G-exercises: 4.14.7(a-b)4.7(c-e)due Tue 14 Feb 9:15am, discussion Tue 14 Feb 12:15pm.

Week V: Random Sampling and Randomized Rounding of Linear Programs (Chapter 5 of WS). U-exercises 5.35.4.
G-exercises: 5.6(a)5.6(b)5.8 (worth 2, 2, 3 points, respectively), due Tue 21 Feb 9:15am, discussion Tue 21 Feb 12:15pm.

Week VI: The Primal-Dual Method (Chapter 7 of WS). U-exercise 7.5.
G-exercises: 7.1 and 7.8 (worth 3 and 2 points, respectively), due Tue 28 Feb 9:15am, discussion Tue 28 Feb 12:15pm.

Week VII: Summary, on Tue 28 Feb. No meeting on Fri 3 Mar.