Extending the Accommodating Function
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen
Eighth Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 2387: 87-96, Springer-Verlag, 2002.

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 the limit of A(alpha) for alpha going towards infinity. 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.


Last modified: September 17, 2002.
Kim Skak Larsen (kslarsen@imada.sdu.dk)