# Approximation Algorithms

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.

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

 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

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

 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