Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Approximation and Online Algorithms - NDMX018

Title:	Aproximační a online algoritmy
Guaranteed by:	Student Affairs Department (32-STUD)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2023
Semester:	summer
E-Credits:	6
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	English
Teaching methods:	full-time
Teaching methods:	full-time
Is provided by:	NDMI018
Additional information:	http://iuuk.mff.cuni.cz/~sgall/vyuka/APX/

Guarantor:	prof. RNDr. Jiří Sgall, DrSc.
Class:	Informatika Mgr. - Diskrétní modely a algoritmy
Classification:	Informatics > Discrete Mathematics
Pre-requisite :	{NXXX007, NXXX008, NXXX009, NXXX036, NXXX037}
Incompatibility :	NDMI018
Interchangeability :	NDMI018

Opinion survey results Examination dates SS schedule Noticeboard

Annotation -

Last update: IUUK (11.05.2015)

For many optimization problems it is impossible to find an optimal solution fast. In such case, it is important to study approximation algorithms that work faster, but the solution they find is not necessarily an optimal one. Sometimes, we also have to react to partial input without knowledge of the complete input, by building a solution step by step. Such algorithms are called on-line. The subject of the course is the study of these two classes of algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms.

Aim of the course -

Last update: IUUK (11.05.2015)

Teach the students selected techniques of design and analysis of approximation and online algorithms.

Course completion requirements -

Last update: prof. RNDr. Jiří Sgall, DrSc. (04.03.2018)

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Literature -

Last update: IUUK (11.05.2015)

D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.

V. V. Vazirani: Approximation Algorithms, Springer, 2001.

A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.

A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.

Requirements to the exam -

Last update: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)

The exam is oral with time for written preparation. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Syllabus -

Last update: IUUK (11.05.2015)

Techniques covered:

Basic definitions, approximation and competitive ratio

Polynomial-time approximation schemes, their relation to strong NP-hardness

Advanced use of linear programming in approximation algorithms: rounding, primal-dual algorithms

Use of semidefinite programming in approximation algorithms

Use of potential functions for online algorithms

Methods for proving the hardness of approximation: L-reductions, APX-completeness, PCP theorem

Problems and algorithms covered:

Various models of scheduling and bin packing, greedy algorithms, further approximation and online algorithms

Combinatorial problems: Steiner trees, maximal cut, coloring

Online algorithms for paging (caching) and k-server problem

Online algorithms for navigation in an unknown environment