The area of online computation deals with the design and analysis of algorithms that run for a potentially unbound time and constantly react to the environment. The computation has to be ongoing and the solution has to be incessantly adjusted to the current situation.

The main property of online algorithms is that they base decisions only on information about the past. They give solutions to common problems in computer systems, economics, and everyday life which are often characterized by the fact hat decisions have to be made under uncertainty about future events.

Due to the frequency in which we encounter online problems in the real world, online algorithms have been and still are extremely extensively studied. They are an essential part of computer science. Typical examples for online problems in computing systems are disk scheduling and memory management, packet routing and forwarding in data networks, and the scheduling of jobs to parallel processors or machines.

We are interest in rigorously investigating all kinds of online problems and to develop and analyze efficient online algorithms that produce provably good quality solutions.

Sample publications:

• M. Englert, H. Röglin, J. Spönemann, and B. Vöcking. Economical Caching. To appear in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS'09), 2009.
• M. Englert, D. Özmen, and M. Westermann. The Power of Reordering for Online Minimum Makespan Scheduling. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pages 603 - 612, 2008.
• M. Englert, H. Räcke, and M. Westermann. Reordering Buffers for General Metric Spaces. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC'07), pages 556 - 564, 2007.
• H. Räcke, C. Sohler, and M. Westermann. Online Scheduling for Sorting Buffers. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA'02), pages 820 - 832, 2002.