- 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 74-79. Springer, 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
seat reservation problem, and the problem of optimizing total flow time
when preemption is allowed.
- 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.
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 by the author.