24th Estonian Winter School in Computer Science (EWSCS)
XXIV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 3 - 8, 2019

Jiří Sgall 

Computer Science Institute
Charles University of 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.

Valid CSS! Valid XHTML 1.0 Strict Last changed March 1, 2019 18:10 Europe/Helsinki (GMT +02:00) by local organizers, ewscs19(at)cs.ioc.ee
EWSCS'19 page: http://cs.ioc.ee/ewscs/2019/