 The Accommodating Function: a generalization of the competitive ratio.
 Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
In 6th International Workshop on Algorithms and Data Structures (WADS), volume 1663 of Lecture Notes in Computer Science, pages 7479. Springer, 1999.
A new measure, the
accommodating function, for the quality
of online algorithms is presented. The accommodating function, which is
a generalization of both the competitive ratio and the accommodating ratio,
measures the quality of an online 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 online problems are investigated: a variant of binpacking 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.

publication
 Link to the publication at the publisher's site  subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.

full version

Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.

other publications

Other publications by the author.