Speaker: Kim Skak Larsen, University of Southern Denmark
Title: On Generally-Applicable Analysis Techniques in Online Algorithms
With a focus on general applicability, we survey selected techniques for determining the relative quality of online algorithms, replacing or refining the standard performance measure of competitive analysis. Then we point to more recent developments, focusing on relaxing the irrevocability requirement for online problems and studying the effects systematically.
The material of this talk is based on joint work with graduate students and other researchers, including Michal Kotrbcik on the most recent material, and with Joan Boyar and Lene Favrholdt as long-term collaborators.