**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)