English DTU.dk Indeks Kontakt Telefonbog Portalen Alumnenetværk
 Søgeord
 Bacheloruddannelser Kandidatuddannelser Ph.d.-uddannelser Diplomuddannelser Bliv ingeniør på DTU DTU kursusbasen Kurser på DTU Informatik Kurser (civilingeniør) Kurser (diplomingeniør) Læs IT på DTU Sommerskole Forskningslaboratorier DTU Match Salg af undervisningsmateriale

## 02908 Design of Approximation Algorithms

### Engelsk titel:

Design of Approximation Algorithms

5

### Kursustype:

 Ph.D.- Matematik, Fysik og Informatik Kurset udbydes under åben uddannelse

Efterår

### Undervisningsform:

Weekly meetings with discussion of the written material and exercises.

### Kursets varighed:

[Kurset følger ikke DTUs normale skemastruktur]

,

### Overordnede kursusmål:

Many interesting discrete optimization problems are NP-hard. Thus, unless P=NP, there are no efficient algorithms to find optimal solutions to such problems. Instead we can relax the requirement of finding an optimal solution, and try to find a solution that approximates the value of the optimal solution. The goal of this course is to gain insight into the key algorithmic techniques used to design and analyze approximation algorithms.

### Læringsmål:

En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
• Prove correctness of approximation algorithms
• Design approximation algorithms for a given problem
• Independently read scientific papers, and describe the contents in a comprehensive manner
• Analyze, evaluate, and compare quality of solutions to problems.
• Apply and extend advanced techniques--e.g. LP-duality, randomized and deterministic rounding, local search, lower bounding techniques --to NP-hard problems to obtain an approximation algorithm
• Show hardness of approximation for a given problem.

### Kursusindhold:

Advanced state-of-the-art techniques for designing approximation algorithms, especially for NP-complete problems. Topics includes clustering, LP-duality, LP-rounding, greedy algorithms, local search, tree metrics, primal-dual method.

### Litteratur:

Design of Approximation Algorithms" by Shmoys and Williamson

### Bemærkninger:

This course is for students with a research interest in algorithms.

The course will consist of weekly meetings, where the text book and solutions to exercises are discussed among the participants. There are no traditional lectures.

### Kursusansvarlig:

Inge Li Gørtz, 322, 018, (+45) 4525 3673,
Philip Bille, 322, 016, (+45) 4525 3647,

### Institut:

02 Institut for Informatik og Matematisk Modellering

### Tilmelding:

Hos læreren
Sidst opdateret: 29. juni, 2012

Åbn kurset i Kursusbasen

 Top
 Matematiktorvet DTU - Bygning 303B 2800 Kgs. Lyngby --- Tlf. 4525 3031 EAN-nr. 5798000428515