๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Revisiting the COUNTER algorithms for list update

โœ Scribed by Susanne Albers; Michael Mitzenmacher

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
579 KB
Volume
64
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Off-line algorithms for the list update
Off-line algorithms for the list update problem
โœ Nick Reingold; Jeffery Westbrook ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 637 KB

Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given; these lead to optimum algorithm which runs in time 02"( n -1) !m, where n is the

Competitive Algorithms for Relaxed List
Competitive Algorithms for Relaxed List Update and Multilevel Caching
โœ Marek Chrobak; John Noga ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 188 KB

We study relaxed list update problem RLUP , in which access requests are made to items stored in a list. The cost to access the jth item x is c , where j j c F c for all i. After the access, x can be repeatedly swapped, at no cost, with i i q1 j any item that precedes it in the list. This problem w