On-line Algorithms

Many real world problems have an on-line component, some decisions that have to be made immediately, before all related data is available. An example of an on-line 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 "off-line", the seat reservation system could wait until it had all reservation requests before assigning any seats. The on-line 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 on-line, as long as the correct on-line algorithm (method of solving the on-line problem) is used. The study of on-line algorithms is aimed at designing and analyzing on-line 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, the competitive ratio. They have recently 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 on-line algorithms) for several problems, including bin packing and paging.

Other on-line problems the group has studied include the seat reservation problem, the TCP acknowledgement problem, and partitioning large BLAST jobs for processing on Grid processors which arrive on-line.

The group has contacts with many other institutions, including University of Haifa, Max Planck Institute für Informatik, University of Bergen, University of California - Irvine, and University of Toronto.

Faculty
Joan Boyar
Lene Monrad Favrholdt
Kim Skak Larsen
Sushmita Gupta (PhD student)
Abyayananda Maiti (PhD student)
Marie Christ (PhD student)