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:
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 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 |
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 |