- The Accommodating Function: a generalization of the competitive ratio.
- Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
SIAM Journal on Computing, 31(1): 233-258, 2001.
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 competitive ratio on accommodating sequences,
measures the quality of an on-line algorithm
as a function of the resources that would be sufficient
for an optimal off-line 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 off-line algorithm will not obtain a better result by
having more than the amount alpha 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 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 bin-packing considered,
we show that
Worst-Fit has a strictly better competitive ratio than
First-Fit, while First-Fit
has a strictly better competitive ratio on accommodating sequences than
- 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 by the author.