Kursusbasen

Kursusoversigt

Kursusbeskrivelse

Kursusnavn (dansk):	Approksimationsalgoritmer
Kursusnavn (engelsk):	Approximation Algorithms
Semester:	Efterår 2002
Udbydes under:	cand.it., internet- og softwareteknologi (int)
Omfang i ECTS:	7,50
Kursussprog:	Engelsk
Kursushjemmeside:	https://learnit.itu.dk
Min. antal deltagere:	0
Forventet antal deltagere:	15
Maks. antal deltagere:	41
Formelle forudsætninger:	Knowledge of basic algorithm theory, such as O-notation, analysis of algorithms, basic complexity classes (P and NP), data structures, graph algorithms, and probabilistic analysis, e.g., as described in Chap. 1-3,5,6-7,10-13,15,17,22-26,34 of \"Introduction to Algorithms\" by Cormen, Leiserson, Rivest, and Stein, MIT Press. It is expected that the students either know these subjects or are able to read it by themselves when needed for the class. Also a certain level of mathematical maturity, as obtained during a undergraduate university mathematics programme or completing an advanced algorithms course is required.
Læringsmål:	The goal of the course is to introduce students to the general algorithmic techniques within approximation algorithms. We will try to build up to the point where students can engage in research on open problems in this area.
Fagligt indhold:	This course explores approximation algorithms, where the goal is to find provably good approximate solutions for optimization problems that are hard to solve exactly. Over the last several years, a number of techniques have emerged for the design of approximation algorithms for a wide variety of problems.We will study approximation algorithms derived from various techniques, such as: Combinatorial algortihms, e.g., greedy algorithms or local search. Liniear programming relaxations via rounding or the primal dual method.
Læringsaktiviteter:	Lectures and exercises.
Eksamensform og -beskrivelse:	X. experimental examination form (7-scale; external exam), 13-skala, Ekstern censur Assignments and oral exam. The oral exam will be graded on the danish 13-scale. The oral exam will consist of a presentation by the student of a research paper. The paper is chosen by student by the end of the semester from a list of possible papers. The presentation should take 20-30 minutes, followed by approximately 10 minutes of questions to the presentation and the paper.
Litteratur udover forskningsartikler:	Vijay V. Vazirani:\"Approximation Algorithms\", Springer 2001, ISBN 3-540-65367-8. Research papers and course notes.