Off-line algorithms for the list update problem
Nick Reingold, Jeffery Westbrook · Information Processing Letters · 1996
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 Θ2n(n − 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. (1988), runs in time Θ(n!)2m.