2011/02/22 by Navin Goyal, Manoj Gupta, Goyal, Navin +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1102.4523
arxiv created 2011/02/22 · arxiv updated 2011/02/23
Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed independently by Lucas and Munro, and they conjectured it to be O(1)-competitive. Recently, Demaine et al. gave a geometric view of the BST problem. This view allowed them to give an online algorithm GreedyArb with the same cost as GreedyFuture. However, no o(n)-competitive ratio was known for GreedyArb. In this paper we make progress towards proving O(1)-competitive ratio for GreedyArb by showing that it is O(log n)-competitive.