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 (or NP-hard) to design an
algorithm that finds an optimal solution fast. In such a case it is
interesting and important to study approximation algorithms that work
faster, at the cost that we find only a good solution, not necessarily an
optimal one. Sometime we are also restricted in our access to the input,
namely we have to react to partial input (typically first few requests of
a long request sequence) without knowledge of the complete input, thus we
are building a solution step by step. Such algorithms are called on-line.
The
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.
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.
Sylabus -
Poslední úprava: IUUK (11.05.2015)
Základní pojmy, aproximační a kompetitivní poměr, polynomiální aproximační schémata.
Různé modely rozvrhování a "bin packing", hladový algoritmus, další aproximační a online algoritmy.
Kombinatorické problémy: nezávislé množiny, "set cover", minimální řez atd.
Použití metod lineárního a semidefinitního programování v aproximačních algoritmech.
Metody pro dokazování obtížnosti i přibližného řešení kombinatorických problémů, tzv. PCP věta.
Online algoritmy pro paging (caching). Tzv. k-server problém.
Podle času a zájmu některé další oblasti: pohyb v neznámém prostředí, směrování v sítích nebo finanční problémy.
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
