TY - GEN

T1 - Extending the Accommodating Function

AU - Boyar, Joan

AU - Favrholdt, Lene Monrad

AU - Larsen, Kim Skak

AU - Nielsen, Morten N.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-45655-4_11

DO - 10.1007/3-540-45655-4_11

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 87

EP - 96

BT - Computing and Combinatorics, 8th Annual International Conference, COCOON 2002

PB - Springer

Y2 - 15 August 2002 through 17 August 2002

ER -