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.


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
Office: 3rd floor, room 307, Malostranské nám. 25

Covered topics

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.


[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

[BM] Benjamin Birnbaum and Claire Mathieu: On-line bipartite matching made simple
ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87.

[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.

[ES1] L. Epstein, J. Sgall: A lower bound for on-line scheduling on uniformly related machines
Oper. Res. Lett., 26(1):17-22, 2000.

[ES2] T. Ebenlendr, J. Sgall: Optimal and online preemptive scheduling on uniformly related machines
In Proc. of the 21st Ann. Symp.  on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci. 2996, pages 199-210. Springer, 2004.

Lecture notes (online)

David Williamson - a course on approximation algorithms: http://iuuk.mff.cuni.cz/~sgall/vyuka/dw-notes2.ps
Avrim Blum - a similar course: http://www-2.cs.cmu.edu/~avrim/Approx00/
Yossi Azar - a similar course: http://www.cs.tau.ac.il/~azar/online03.html

Previous run of the course in Czech in 2018

Probraná látka podle přednášek v r. 2018

Další plán podle předchozího běhu