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 of resources.

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 Worst-Fit.

---

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.