2004/12/23 by Erik D. Demaine, Dion Harmon, John Iacono +1 · 2 citations
Computer Science · Decision Sciences · #Optimization and Search Problems #Advanced Bandit Algorithms Research #Auction Theory and Applications
paper · doi:10.1109/focs.2004.23
openalex publication_date 2004/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan's dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist.