 The Accommodating Function: a generalization of the competitive ratio.
 Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
SIAM Journal on Computing, 31(1): 233258, 2001.
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 competitive ratio on accommodating sequences,
measures the quality of an online algorithm
as a function of the resources that would be sufficient
for an optimal offline algorithm to fully grant all requests.
More precisely, if we have some amount of resources
n,
the function value at
alpha is the usual ratio (still on
some fixed amount of resources
n), except that input sequences
are restricted to those
where the optimal offline algorithm will not obtain a better result by
having more than the amount
alpha n of resources.
The accommodating functions for
three specific online problems are investigated: a variant of binpacking in
which the goal is to maximize the number of items put in n bins, the
Seat Reservation Problem, and the problem of optimizing total flow time
when preemption is allowed.
We also show that when trying to distinguish between two algorithms,
the decision as to which one performs better cannot necessarily be made
from the competitive ratio or the competitive ratio on
accommodating sequences alone.
For the variant of binpacking considered,
we show that
WorstFit has a strictly better competitive ratio than
FirstFit, while FirstFit
has a strictly better competitive ratio on accommodating sequences than
WorstFit.

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

open access (328 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.