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.
Last update: IUUK (11.05.2015)
Pro mnohé optimalizační problémy je obtížné navrhnout algoritmy, které je vyřeší optimálně a zároveň rychle
(např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a
najdou řešení více či méně blízké optimálnímu řešení. Tzv. online algoritmy se studují v situaci, kde není předem
znám celý vstup. Přednáška se zaměří na teoretické studium aproximačních a online algoritmů pro různé
problémy. Předpokládá se znalost na úrovni Bc. předmětu NDMI084 Úvod do aproximačních a
pravděpodobnostních algoritmů.
Aim of the course -
Last update: IUUK (11.05.2015)
Teach the students selected techniques of design and analysis of approximation and online algorithms.
Last update: IUUK (11.05.2015)
Naučit středně pokročilé techniky návrhu a analýzy aproximačních a online algoritmů.
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.
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.
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
