Name
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 reorganiza- tion rule, which applies to all possible distributions. In this paper we show that for a list of n elements, arbitrary request probabilities and α 0, the expected cost under CS achieves a ratio of at most 1 α to the optimal (minimal) expected cost within Qn lgn α2 reorganization steps, for a Q we can compute. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009245 | Algorithmica |
Keywords | Field | DocType |
Key words. List update problem,Counter scheme,Self-organizing data structures,Average case analysis. | Discrete mathematics,Data structure,Combinatorics,List update problem,Algorithm complexity,A priori and a posteriori,Self-organization,Algorithm,Expected cost,List processing,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 4 | 0178-4617 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hadas Shachnai | 1 | 960 | 78.85 |
| Micha Hofri | 2 | 342 | 127.96 |