Optimum off-line algorithms for the list update problem
| Author(s) : | Jeffery Westbrook Nick Reingold, |
| Publisher : | N/A |
| Publication Date : | 1990 |
| ISSN : | N/A |
| Abstract : | 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 \Theta2 n (n \Gamma 1)!m, where n is the length of the list and m is the number of requests. The previous best algorithm, an adaptation of a more general algorithm due to Manasse et al. [9], runs in time \Theta(n!) 2, |