TY - GEN

T1 - The Accommodating Function

T2 - Sixth International Workshop on Algorithms and Data Structures

AU - Boyar, Joan

AU - Larsen, Kim Skak

AU - Nielsen, Morten N.

PY - 1999

Y1 - 1999

N2 - A new measure, the accommodating function, for the quality of on-line algorithms is presented. The accommodating function, which is a generalization of both the competitive ratio and the accommodating ratio, measures the quality of an on-line algorithm as a function of the resources that would be sufficient for some algorithm to fully grant all requests. More precisely, if we have some amount of resources n, the function value at α is the usual ratio (still on some fixed amount of resources n), except that input sequences are restricted to those where all requests could have been fully granted by some algorithm if it had had the amount of resources αn. The accommodating functions for two specific on-line problems are investigated: a variant of bin-packing in which the goal is to maximize the number of objects put in n bins and the seat reservation problem.

AB - A new measure, the accommodating function, for the quality of on-line algorithms is presented. The accommodating function, which is a generalization of both the competitive ratio and the accommodating ratio, measures the quality of an on-line algorithm as a function of the resources that would be sufficient for some algorithm to fully grant all requests. More precisely, if we have some amount of resources n, the function value at α is the usual ratio (still on some fixed amount of resources n), except that input sequences are restricted to those where all requests could have been fully granted by some algorithm if it had had the amount of resources αn. The accommodating functions for two specific on-line problems are investigated: a variant of bin-packing in which the goal is to maximize the number of objects put in n bins and the seat reservation problem.

U2 - 10.1007/3-540-48447-7_9

DO - 10.1007/3-540-48447-7_9

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 74

EP - 79

BT - Algorithms and Data Structures, 6th International Workshop, WADS '99

PB - Springer

Y2 - 11 August 1999 through 14 August 1999

ER -