RANDOMIZED COMPETITIVE ALGORITHMS FOR SUCCESSFUL AND UNSUCCESSFUL SEARCH

This paper studies the classical dictionary problem using a self-adjus ting linear list. We designed and analyzed randomized, on-line algorit hms for a sequence of successful and unsuccessful searches which are c ompetitive with off-line algorithms. Our algorithms combined the ps bi t technique which speeds up unsuccessful search with the randomized mo ve-to-front scheme of Reingold et al., which they used to speed up suc cessful search.