Extending the Accommodating Function.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
In 8th Annual International Computing and Combinatorics Conference (COCOON), volume 2387 of Lecture Notes in Computer Science, pages 87-96. Springer, 2002.

The applicability of the accommodating function, a relatively new measure for the quality of on-line algorithms, is extended. If a limited amount n of some resource is available, the accommodating function A(alpha) is the competitive ratio when input sequences are restricted to those for which the amount alpha n of resources suffices for an optimal off-line algorithm. The standard competitive ratio is the limit of A(alpha) for alpha going towards infinity. The accommodating function was originally used only for alpha >= 1. We focus on alpha < 1, observe that the function now appears interesting for a greater variety of problems, and use it to make new distinctions between known algorithms and to find new ones.

---

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.