2 papers
cs.DS2026
The Greedy Binary Search Tree is Non-trivially Competitive
Yuhao Guo, Seth Pettie, Daniel Skora +1
We prove that the binary search tree is -competitive. It is widely conjectured that is -competitive, but before…
cs.CG2025
The Squishy Grid Problem
Zixi Cai, Kuowen Chen, Shengquan Du +3
In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the…