Computer Science – Data Structures and Algorithms
Scientific paper
2011-02-22
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Goyal Navin
Gupta Manoj
No associations
LandOfFree
On Dynamic Optimality for Binary Search Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Dynamic Optimality for Binary Search Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Dynamic Optimality for Binary Search Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-559455