𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Randomized Competitive Algorithms for Generalized Caching

✍ Scribed by Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)

Book ID
118159069
Publisher
Society for Industrial and Applied Mathematics
Year
2012
Tongue
English
Weight
303 KB
Volume
41
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

More on randomized on-line algorithms fo
More on randomized on-line algorithms for caching
✍ Marek Chrobak; Elias Koutsoupias; John Noga πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 143 KB

We address the tradeo between the competitive ratio and the resources used by randomized on-line algorithms for caching. Two algorithms reported in the literature that achieve the optimal ratio H k require a lot of memory and perform extensive computation at each step. On the other hand, a very simp

Competitive analysis of randomized pagin
Competitive analysis of randomized paging algorithms
✍ Dimitris Achlioptas; Marek Chrobak; John Noga πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 130 KB

The paging problem is deΓΏned as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p,

Placement Algorithms for Hierarchical Co
Placement Algorithms for Hierarchical Cooperative Caching
✍ Madhukar R Korupolu; C.Greg Plaxton; Rajmohan Rajaraman πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 286 KB

Consider a hierarchical network in which each node periodically issues a request for an object drawn from a fixed set of unit-size objects. Suppose further that the following conditions are satisfied: the frequency with which each node accesses each object is known; each node has a cache of known ca