In pursuit of the dynamic optimality conjecture

DOI10.1007/978-3-642-40273-9_16MaRDI QIDQ2848978zbMATH OpenOpenAlexFDO

Authors John Iacono

Publication date 13 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.0207

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence---any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.

Recommendations

• scientific article; zbMATH DE number 5237331
• A study on splay trees
• A new path from Splay to dynamic optimality
• Dynamic Optimality—Almost
• Self-adjusting binary search trees

Cites work

• A unified access bound on comparison-based dynamic dictionaries
• An Explanation of Splaying
• Combining binary search trees
• De-amortizing binary search trees
• Dynamic Optimality—Almost
• Lower Bounds for Accessing Binary Search Trees with Rotations
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Self-adjusting binary search trees
• Self-Organizing Binary Search Trees
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Static optimality and dynamic search-optimality in lists and trees
• The multiplicative weights update method: a meta-algorithm and applications
• Upper bounds for maximally greedy binary search trees

Cited in

(24)

• Static optimality and dynamic search-optimality in lists and trees
• A study on splay trees
• Better analysis of binary search tree on decomposable sequences
• On optimality gaps in the Halfin-Whitt regime
• The dynamic optimization of PKM
• Greedy is an almost optimal deque
• Self-adjusting binary search trees: what makes them tick?
• Effective splaying with restricted rotations
• scientific article; zbMATH DE number 124845 (Why is no real title available?)
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• scientific article; zbMATH DE number 2119638 (Why is no real title available?)
• Pairing heaps: the forward variant
• Multi-Finger Binary Search Trees
• Smooth heaps and a dual view of self-adjusting data structures
• A new path from Splay to dynamic optimality
• Dynamic Optimality—Almost
• scientific article; zbMATH DE number 3317548 (Why is no real title available?)
• scientific article; zbMATH DE number 7651207 (Why is no real title available?)
• Belga B-trees
• Competitive Online Search Trees on Trees
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• Continuous alternation: the complexity of pursuit in continuous domains
• Hardness amplification for dynamic binary search trees
• The envelope theorem in dynamic optimization

This page was built for publication: In pursuit of the dynamic optimality conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848978)