The Accommodating Function: a generalization of the competitive ratio

Joan Boyar, Kim Skak Larsen, Morten N. Nielsen

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

Abstrakt

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 α 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 αn. The accommodating functions for two 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 and the seat reservation problem.
OriginalsprogEngelsk
TitelAlgorithms and Data Structures, 6th International Workshop, WADS '99
Antal sider6
ForlagSpringer
Publikationsdato1999
Sider74-79
DOI
StatusUdgivet - 1999
BegivenhedSixth International Workshop on Algorithms and Data Structures - Vancouver, Canada
Varighed: 11. aug. 199914. aug. 1999

Konference

KonferenceSixth International Workshop on Algorithms and Data Structures
LandCanada
ByVancouver
Periode11/08/199914/08/1999
NavnLecture Notes in Computer Science
Vol/bind1663

Fingeraftryk

Dyk ned i forskningsemnerne om 'The Accommodating Function: a generalization of the competitive ratio'. Sammen danner de et unikt fingeraftryk.

Citationsformater