Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. In this work, we attempt to lay the foundations for a proof of the dynamic optimality conjecture.
Central to our methods are simulation embeddings and approximate monotonicity. A simulation embedding maps each execution to a list of keys that induces a target algorithm to simulate the execution. Approximately monotone algorithms are those whose cost does not increase by more than a constant factor when keys are removed from the list. Approximately monotone algorithms with simulation embeddings are dynamically optimal. Building on these concepts, we present the following results:
1. We build a simulation embedding for Splay by inducing Splay to perform arbitrary subtree transformations. Thus, if Splay is approximately monotone then it is dynamically optimal. We also show that approximate monotonicity is a necessary condition for dynamic optimality.
2. We show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests.
3. We prove that a known lower bound on optimal execution cost by Wilber is approximately monotone.
4. We speculate about how one might establish dynamic optimality by adapting the proof of approximate monotonicity from the lower bound to Splay.
5. We show that the related traversal and deque conjectures also follow if Splay is approximately monotone, and generalize our main results to a broad class of "path-based" algorithms.
|Advisor:||Tarjan, Robert E.|
|Commitee:||Chazelle, Bernard, Mehlhorn, Kurt, Sedgewick, Robert, Tarjan, Robert E.|
|Department:||Applied and Computational Mathematics|
|School Location:||United States -- New Jersey|
|Source:||DAI-B 80/11(E), Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Computer science|
|Keywords:||Additive overhead, Approximate monotonicity, Dynamic optimality, Simulation embedding, Splay trees, Subtree transformations|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be