Online algorithms deal with a particularly challenging branch of the algorithms area. Many real world problems have an online component, some decisions that have to be made immediately, before all related data is available. An example of an online problem is the seat reservation problem, where, as with the IC trains in Denmark, a given train has a fixed number of seats and passengers can make seat reservations before their trip and be given seat numbers immediately. In contrast, if the problem were "offline", the seat reservation system could wait until it had all reservation requests before assigning any seats. The online property limits how well a system can perform in optimizing for its objective (maximizing the number of passengers able to buy tickets, for example). However, it may be possible for a system to perform quite well, even if the problem is online, as long as the correct online algorithm (method of solving the online problem) is used. The study of online algorithms is aimed at designing and analyzing online algorithms.

In analyzing algorithms, it is very useful to have a theoretical tool which can be used in predicting how well algorithms will do in practice. The group has been working extensively on this, concentrating on alternatives to the standard quality measure for online algorithms, the competitive ratio. They have defined and are investigating the relative worst order ratio, which gives results superior to those obtained with competitive analysis (the standard measure for the quality of online algorithms) for several problems, including bin packing and paging.

Newer activities include the investigation of advice complexity issues. The advice complexity of a problem is a measure of the amount of advance knowledge of the sequence is necessary to achieve a certain performance. The group has used advice complexity to define the first complexity classes for online problems. In extension of this work, we have broadened our scope within algorithms dealing with uncertainty, and we have recently focused on online algorithms with predictions. Among other things, this opens up for an integration of machine learning components with the online algorithms. The models for this topic are under development in an international context, but the overall focus is on establishing results that are good both with regards to consistency (the algorithm does well when the predictions are good) and robustness (the algorithm comes with some reasonable guarantees even when predictions are bad.

Most of the problems we address focus on minimizing resource consumption. This relates to energy consumption and therefore environmental protection, but also to resource management in general to facilitate cost-effective production and solutions in general.

Some concrete online problems the group has studied include the seat reservation problem, bin packing with applications for numerous packing problems for boxes and containers, paging issues for caching in computer systems, the TCP acknowledgement problem, graph coloring, frequency assignment for moving cell phones, and various scheduling problems, including partitioning large BLAST jobs for processing on Grid processors arriving online.

The group is part of the much larger Algorithms Group. The Algorithms Group consists of three subgroups of which Online Algorithms is one.