25th Estonian Winter School in Computer Science (EWSCS)
XXV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1 - 6, 2020

Jiří Sgall 

Computer Science Institute
Charles University
Prague, Czech Republic

Online algorithms

Abstract

The purpose of this course is to survey basic problems and techniques in online algorithms. The paradigm of online algorithms concerns situations when an algorithm recieve an input gradually, yet it is required to produce partial solutions based on the partial inputs. Such situations appear widely in operating systems and computing, in manufacturing, in datastructures etc. The area of online algoritms provides a systematic way to treat such situations from the viewpoint of theory of algorithms.

We will cover classical problems such as bin packing, scheduling and k-server problem, and techniques that appear often in this area such as adversary techniques for lower bounds, potential functions and weight functions for upper bounds. One area of focus will be the use of randomization in online algorithms.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed April 10, 2020 22:32 Europe/Helsinki (GMT +03:00) by local organizers, ewscs20(at)cs.ioc.ee
EWSCS'20 page: //cs.ioc.ee/ewscs/2020/