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ů.
Poslední úprava: 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.
Cíl předmětu -
Poslední úprava: IUUK (11.05.2015)
Naučit středně pokročilé techniky návrhu a analýzy aproximačních a online algoritmů.
Poslední úprava: IUUK (11.05.2015)
Teach the students selected techniques of design and analysis of approximation and online algorithms.
Podmínky zakončení předmětu -
Poslední úprava: 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.
Poslední úprava: 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.
Literatura -
Poslední úprava: 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.
Poslední úprava: 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.
Požadavky ke zkoušce -
Poslední úprava: 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.
Poslední úprava: 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.
Sylabus -
Poslední úprava: IUUK (11.05.2015)
Probírané techniky:
Základní pojmy, aproximační a kompetitivní poměr
Polynomiální aproximační schémata, jejich vztah k silné NP-úplnosti
Pokročilé použití metod lineárního programování v aproximačních algoritmech: zaokrouhlování, primárně-duální algoritmy
Použití metod semidefinitního programování v aproximačních algoritmech
Použití potenciálu pro online algoritmy
Metody pro dokazování obtížnosti i přibližného řešení kombinatorických problémů: L-redukce, APX-úplnost, PCP věta
Probírané problémy a algoritmy:
Různé modely rozvrhování a "bin packing", hladový algoritmus, další aproximační a online algoritmy
Kombinatorické problémy: Steinerův strom, maximální řez, barvení grafů
Online algoritmy pro paging (caching) a k-server problém
Online algoritmy pro pohyb v neznámém prostředí
Poslední úprava: 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
