ALCOMFT-TR-02-4

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen and Morten N. Nielsen
Extending the Accommodating Function
Århus. Work package 4. March 2002.

Abstract: The applicability of the accommodating function, a relatively new measure for the quality of on-line algorithms, is extended. If a limited amount n of some resource is available, the accommodating function A(alpha) is the competitive ratio when input sequences are restricted to those for which the amount alpha n of resources suffices for an optimal off-line algorithm. The standard competitive ratio is \lim_{alpha-> \infty}A(alpha). The accommodating function was originally used only for alpha>= 1. We focus on alpha<1, observe that the function now appears interesting for a greater variety of problems, and use it to make new distinctions between known algorithms and to find new ones.

Postscript file: ALCOMFT-TR-02-4.ps.gz (201 kb).