Extending the Accommodating Function

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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 (α) is the competitive ratio when input sequences are restricted to those for which the amount α n of resources suffices for an optimal off-line algorithm. The accommodating function was originally used only for α ≥ 1. We focus on α < 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.
OriginalsprogEngelsk
TitelComputing and Combinatorics, 8th Annual International Conference, COCOON 2002
ForlagSpringer
Publikationsdato2002
Sider87-96
DOI
StatusUdgivet - 2002
BegivenhedEighth Annual International Computing and Combinatorics Conference - , Singapore
Varighed: 15. aug. 200217. aug. 2002

Konference

KonferenceEighth Annual International Computing and Combinatorics Conference
LandSingapore
Periode15/08/200217/08/2002
NavnLecture Notes in Computer Science
Vol/bind2387

Citationsformater