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

A lower bound for randomized list update algorithms

โœ Scribed by Boris Teia

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
405 KB
Volume
47
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A lower bound for partial list colorings
A lower bound for partial list colorings
โœ Chappell, Glenn G. ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 188 KB ๐Ÿ‘ 2 views

Let G be an n-vertex graph with list-chromatic number ฯ‡ . Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t n /ฯ‡ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a coroll

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