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ů.
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.
Last update: prof. RNDr. Jiří Sgall, DrSc. (04.03.2018)
Pro získání je zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru za podmínky účasti studenta na cvičeních. Při neúčasti jsou potřeba dvě třetiny z celkového počtu bodů. Povaha kontroly studia neumožňuje opakování zápočtu.
Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.
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.
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.
Last update: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)
Zkouška je ústní s písemnou přípravou. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.
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