**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 *a**n*.
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)