News Connections For Students Contact

Research Areas

Online Algorithms

Online problems are optimization problems where the input arrives one request at a time, and each request must be processed without knowledge of future requests. The investigation of online algorithms was largely initiated by the introduction of competitive analysis by Sleator and Tarjan. They introduced the method as a general analysis technique, inspired by approximation algorithms. The term ``competitive'' is from Karlin et al. who named the worst-case ratio of the performance of the online to the offline algorithm the "competitive ratio". Many years earlier, Graham carried out what is now viewed as an example of a competitive analysis.

The over-all goal of a theoretical quality measure is to predict behavior of algorithms in practice. In that respect, competitive analysis works well in some cases, but, as pointed out by the inventors and others, fails to discriminate between good and bad algorithms in other cases. Ever since its introduction, researchers have worked on improving the measure, defining variants, or defining measures based on other concepts to improve on the situation. Relative worst-order analysis (RWOA), a technique for assessing the relative quality of online algorithms, is one of the most thoroughly tested such proposals.

RWOA was originally defined by Boyar and Favrholdt, and the definitions were extended together with Larsen. As for all quality measures, an important issue is to be able to separate algorithms, i.e., determine which of two algorithms is the best. RWOA has been shown to be applicable to a wide variety of problems and provide separations, not obtainable using competitive analysis, corresponding better to experimental results or intuition in many cases.

The group has written a survey of this area, where we motivate and define RWOA, outline the background for its introduction, survey the most important results, and compare it to other measures.

A significant part of the groups work on online algorithm has dealt with this measure, but also with other issues having to do with improving the accuracy of prediction of the behavior of online algorithms.

Advice Complexity

In online scenarios requests arrive over time, and each request must be serviced in an irrevocable manner before the next request arrives. Online algorithms with advice is an area of research where one attempts to measure how much knowledge of future requests is necessary to achieve a given performance level, as defined by the competitive ratio. When this knowledge, the advice, is obtainable, this leads to practical algorithms, called semi-online algorithms. On the other hand, each negative result gives robust results about the limitations of a broad range of semi-online algorithms.

The group has written a survey, where we explain the models for online algorithms with advice, motivate the study in general, present some examples of the work that has been carried out, and include a quite complete set of references, organized by problem studied. The group has been involved in many of these results.