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 (α) is the competitive ratio when input sequences are restricted to those for which the amount α n of resources suffices for an optimal off-line algorithm. The accommodating function was originally used only for α ≥ 1. We focus on α < 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.
|Konference||Eighth Annual International Computing and Combinatorics Conference|
|Periode||15/08/2002 → 17/08/2002|
|Navn||Lecture Notes in Computer Science|