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