Weekly meetings with discussion of the written material and exercises.
Kursets varighed:
[Kurset følger ikke DTUs normale skemastruktur]
Evalueringsform:
Hjælpemidler:
Bedømmelsesform:
Faglige forudsætninger:
,
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.
