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 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.


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.


Some on-line problems the group has studied include the seat reservation problem, bin packing, paging, the TCP acknowledgement problem, graph coloring, and various scheduling problems, including partitioning large BLAST jobs for processing on Grid processors arriving on-line.


The group has strong contacts with many other institutions, including ETH, University of Haifa, University of Bergen, University of California - Irvine, University of Toronto, University of Leicester, and University of Waterloo.



Joan Boyar 
Lene Monrad Favrholdt 
Kim Skak Larsen 


To give you the best possible experience, this site uses cookies Read more about cookies

Accept cookies