The Accommodating Function - a generalization of the competitive ratio
Joan Boyar, Kim S. Larsen, Morten N. Nielsen
Sixth International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 1663: 74-79, Springer-Verlag, 1999.

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 a 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 an. The accommodating functions for three 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, the seat reservation problem, and the problem of optimizing total flow time when preemption is allowed.


Last modified: August 17, 1999.
Kim Skak Larsen (kslarsen@imada.sdu.dk)

 


   Data protection at SDUDatabeskyttelse på SDU