Susanne Albers, University of Freiburg, Germany

On-line algorithms
Many computational problems that arise in practice are inherently online. In these problems the input arrives incrementally over time; whenever a new input portion arrives, an algorithm has to generate output not knowing future input. Over the past 15 to 20 years, the design and analysis of online algorithms has received tremendous research interest. In the first part of this lecture series we will study classical results in the theory of online algorithms. More specifically, we will present fundamental results on scheduling, self-organizing lists, paging and the power of randomization in online algorithms. Many of the results can be found in the text book by Borodin and El-Yaniv. In the second part of the lectures we will investigate online problems in application areas of current interest. These include algorithmic problems in large networks, energy-efficient scheduling, robotics or online auctions.

References
A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.

A. Blum, P. Raghavan and B. Schieber. Navigating in unfamiliar geometric terrain. SIAM Journal on Computing, 26:110-137, 1997.

A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber and M. Sviridenko. Buffer overflow management in QoS switches. SIAM Journal on Computing, 33:563-583, 2004.

R. Lavi and N. Nisan. Competitive analysis of incentive compatible on-line auctions. ACM Conference on Electronic Commerce, 233-241,2000.

F.F. Yao, A.J. Demers, S. Shenker. A scheduling model for reduced CPU energy. 36th Annual Symposium on Foundations of Computer Science, 374-382, 1995.