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.

Grading policy:

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.


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


Date Topic
Book chapter
Week 1
Introduction, Vertex cover, Set cover, Greedy Algorithms.
ch. 1, 2
Week 2
Steiner tree, TSP. Cuts.
ch. 3, 4
Week 3
Approximation Schemes, FPTAS, PTAS. Knapsack, Multiprocessors Scheduling.
ch. 8, 10
Week 4
Linear Programming techniques.
ch. 12
Week 5
Rounding Technique (lecture scribed by Finn R. Jensen).
ch. 13, 14, 15
Week 6
Primal-Dual Technique.
ch. 22, 23
Week 7
ch. 29


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]".

Date Assignment
Due date
Week 1 1.1, 1.3, 1.7, 2.11 (solve one in your choice) and the class problem.
Feb 1st
Week 2 3.2, 3.3, 4.2 (solve one in your choice) and the class problem (a solution).
Feb 8th
Week 3 homework 3 (a solution and other one.)
Feb 18th
Week 4 homework 4 (a solution)
Feb 25th
Week 5 22.7
Mar 8th

Exam Schedule:

30 March 2010 31 March 2010
10h00: Troels Haln
10h00: Finn Jensen
10h20: Clement Maria
10h20: Dan Thomsen
10h40: Valerio Bruno
10h40: Thor Soerensen
11h00: Simone Weikl
11h00: Eivind Simonsen
11h20: Kasper Larsen
13h30: Kristian Kristensen
13h50: Mathias Ingesman
14h10: Magnus Madsen
14h30: Kaare Soerensen
15h00: Kim Petersen
15h20: Mikkel Haugaard
15h40: Kristian Hjorth
16h00: Morten Schaumburg