東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

New Paths from Splay to Dynamic Opti...

Levy, Caleb Carson.

Linked to FindBook

Google Book

Amazon

博客來

New Paths from Splay to Dynamic Optimality.

Record Type:	Electronic resources : Monograph/item
Title/Author:	New Paths from Splay to Dynamic Optimality./
Author:	Levy, Caleb Carson.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2019,
Description:	137 p.
Notes:	Source: Dissertations Abstracts International, Volume: 80-12, Section: B.
Contained By:	Dissertations Abstracts International80-12B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13885892
ISBN:	9781392271278

New Paths from Splay to Dynamic Optimality.
Levy, Caleb Carson.

New Paths from Splay to Dynamic Optimality. - Ann Arbor : ProQuest Dissertations & Theses, 2019 - 137 p.

Source: Dissertations Abstracts International, Volume: 80-12, Section: B.

Thesis (Ph.D.)--Princeton University, 2019.

This item must not be sold to any third party vendors.

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.

ISBN: 9781392271278Subjects--Topical Terms:

1669109
Applied Mathematics.

New Paths from Splay to Dynamic Optimality.
LDR:03284nmm a2200325 4500 001 2210831
005 20191121124318.5
008 201008s2019 ||||||||||||||||| ||eng d
020 $a 9781392271278
035 $a (MiAaPQ)AAI13885892
035 $a (MiAaPQ)princeton:13029
035 $a AAI13885892
040 $a MiAaPQ $c MiAaPQ
100 1 $a Levy, Caleb Carson. $3 3437973
245 1 0 $a New Paths from Splay to Dynamic Optimality.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2019
300 $a 137 p.
500 $a Source: Dissertations Abstracts International, Volume: 80-12, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Tarjan, Robert E.
502 $a Thesis (Ph.D.)--Princeton University, 2019.
506 $a This item must not be sold to any third party vendors.
520 $a 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.
590 $a School code: 0181.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Computer science. $3 523869
690 $a 0364
690 $a 0984
710 2 $a Princeton University. $b Applied and Computational Mathematics. $3 3182352
773 0 $t Dissertations Abstracts International $g 80-12B.
790 $a 0181
791 $a Ph.D.
792 $a 2019
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13885892