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.
- J. Sgall. Online algorithms. Slides from EWSCS 2020.
- Videos from the lectures (large, unedited files) [mp4, password-protected]
- Literature list
April 10, 2020 22:32 Europe/Helsinki (GMT +03:00)
local organizers, ewscs20(at)cs.ioc.ee
EWSCS'20 page: //cs.ioc.ee/ewscs/2020/