scientific article; zbMATH DE number 7758335

DOI10.4230/lipics.approx/random.2020.33arXiv1912.02900MaRDI QIDQ6062157

Parinya Chalermsook, Thatchaphol Saranurak, Julia Chuzhoy

Publication date: 31 October 2023

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

binary search treesdynamic optimalityWilber bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The power and limitations of static binary search trees with lazy finger
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
• Sequential access in splay trees takes linear time
• On the deque conjecture for the splay algorithm
• On the sequential access theorem and deque conjecture for splay trees
• Symmetric binary B-trees: Data structure and maintenance algorithms
• In Pursuit of the Dynamic Optimality Conjecture
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Greedy Is an Almost Optimal Deque
• O(log log n)-competitive dynamic binary search trees
• Self-adjusting binary search trees
• 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
• Dynamic Optimality—Almost