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.