NDMI018 - Aproximační a online algoritmy
Approximation and Online Algorithms
LS/Spring 2020 - Jiří Sgall
Monday, 12:20, S9
CORONAVIRUS UPDATE: We have regular online classes, they are
also recorded, see the links below
The language of the class will be English, the page will be
converted gradually.
Syllabus
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.
Contact info
E-mail: last name at iuuk.mff.cuni.cz
Phone: 951 554 293 http://iuuk.mff.cuni.cz/~sgall/
Office: 3rd floor, room 307, Malostranské nám. 25
Covered topics
1. (Feb 27)
introduction, approximation ratio, examples from previous
course
online preemptive scheduling on uniformly related machines
lower bounds for preemptive and nonpreemptive scheduling
on related machines [ES1]
online matching [BM]
12. (May 25)
online matching - recap
PCP theorem and its applications, gap preserving reduction,
examples [WS 16.3]
12. (June 1)
hardness of clique
unique games conjecture [WS 13.3, WS 16.5]
Study materials
For approximation algorithms the most up-to-date is the book by
Williamson-Shmoys, I also recommend lecture notes by Williamson and
the book by Vazirani. For onlines algorithm for paging and k-server
I recommend the book by Borodin and El-Yaniv. For scheduling and
online matching, I give pointers to some additional papers.
Textbooks
[WS] D. P. Williamson, D. B. Shmoys: The Design of
Approximation Algorithms, Cambridge university press, 2011.
[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.
[BE] A. Borodin, R. El-Yaniv: Online computation and competitive
analysis. Cambridge university press, 1998.
[FG] A. Fiat, G. Woeginger: Online Algorithms - The State of
the Art, LNCS 1442, Springer, 1998.
J. Hromkovic: Algorithmics for Hard Problems, Springer, 2001.
G. Ausiello et al: Complexity and Approximation, Springer, 1999.
D. S. Hochbaum (editor): Approximation algorithms for NP-hard
problems, PWS publishing company, 1997. Papers
[S] J. Sgall: On-line
scheduling
In Online Algorithms: The State of the Art, eds.A. Fiat
and G. J. Woeginger, Lecture Notes in Comput. Sci. 1442, pages
196-231, Springer, 1998.