Approximation Algorithms

Administration Information

Instructors: Nguyen Kim Thang.
Time: Tuesday 12-14, Friday 10-12
Location: Shannon-157
Prerequisites: Optimization (may be followed simultaneously) and a reasonable background in algorithms and discrete mathematics would be needed.
Bibliography:

• Course notes.
• An excellent book Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag Berlin Heidelberg.

Grading policy:

• Homework: There will be a set of exercises for each week and you are encouraged to work on, write up and turn in some exercises depending on the requirement.
• Exam: oral in 20-30 minutes.
• Project (for students follows honor course): Read and present a research paper in 25'.

Examination: date: 30, 31 March, location: Turing 030 + 031 and schedule.

Program of the exam: everything related to the lectures and read chapter 24, Approximation Algorithms.

Reading paper (Honor project): Approximating Minimum Bounded Degree Spanning Tree to Within One of Optimal (one can start by reading Iterative Rounding Technique in Section 23, Approximation Algorithms book).

Course description

How does one deal with NP-hard problems? For optimization problems, one possibility is to attempt to find, in polynomial time, a solution which is guaranteed to have value relatively close to optimal. This is the approach taken in the design of approximation algorithms. Such algorithms are one robust way to cope with intractable problems that arise in many areas of Computer Science and beyond.

The course focuses on the design and analysis of polynomial time approximation algorithms with proven performance guarantees for NP-hard optimization problems. The goal is to understand techniques and algorithmic paradigms which have wide applicability. In particular, we will study concrete problems from graph theory to scheduling (for example, Set Cover, Steiner trees, Facility Location, ...) and design, analyze algorithms using techniques of greedy algorithms, local search or technique based on linear programming.

Objectives

The participant will after the course have insight into the design of approximation algorithms and knowledge of basic techniques for approximation algorithms.

Schedule:

Homework:

The set of exercises is given in Tuesday and the homework is usually due no later than midnight of the next Monday (see due date). Students will be asked to solve one or two exercises in their choices. It is recommended that you work in group of 2 but the write up is individual and you should mention the other in the group. It is also encouraged that you do not individually or work with the same person on more than 3 assignments. For those who want to type in Latex, here is a template.

Your homework should contain your name and the assignment number in the file's name. Emails should contain "[Approx'10]".

Exam Schedule: