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
T2 - Eighth Annual International Computing and Combinatorics Conference
Y2 - 15 August 2002 through 17 August 2002
ER -