Instructors: Nguyen Kim Thang.
Time: Tuesday 1214, Friday 1012
Location: Shannon157
Prerequisites: Optimization (may be followed simultaneously) and a reasonable background in algorithms and discrete mathematics would be needed.
Bibliography:
Grading policy:
Examination: and schedule.
Program of the exam: everything related to the lectures and read , 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).
How does one deal with NPhard 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 NPhard 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 
PrimalDual Technique. 
ch. 22, 23 
Week 7 
Inapproximability. 
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 
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 