Show simple item record

dc.contributor.authorHofri, Micha
Shachnai, Hadas
dc.date.accessioned 2017-08-02T22:03:38Z
dc.date.available 2017-08-02T22:03:38Z
dc.date.issued 1998-02-02
dc.identifier.urihttps://hdl.handle.net/1911/96483
dc.description.abstract We consider the problem of dynamic reorganization of a linear list, where requests for the elements are generated randomly with fixed, unknown probabilities. The objective is to obtain the smallest expected cost per access. It has been shown, that when no a-priori information is given on the reference probabilities, the Counter Scheme (CS) provides an optimal reorganization rule, which applies to {\em all} possible distributions. In this paper we show that for a list of n elements, arbitrary probabilities and any alpha in (0,1), the cost under CS approaches the minimal expected cost up to a ratio of 1 + alpha in O(n lg n alpha^2) reorganization steps.
dc.format.extent 9 pp
dc.language.iso eng
dc.rights You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of forty-five (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).
dc.title The List Update ProblemImproved Bounds for the Counter Scheme
dc.type Technical report
dc.date.note February 2, 1998
dc.identifier.digital TR98-300
dc.type.dcmi Text
dc.identifier.citation Hofri, Micha and Shachnai, Hadas. "The List Update ProblemImproved Bounds for the Counter Scheme." (1998) https://hdl.handle.net/1911/96483.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record