English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Consider the task of performing a sequence of searches in a binary searchtree. After each search, we allow an algorithm to arbitrarily restructure thetree. The cost of executing the task is the sum of the time spent searching andthe time spent optimizing the searches with restructuring operations. Sleatorand Tarjan introduced this notion in 1985, along with an algorithm and aconjecture. The algorithm, Splay, is an elegant procedure for performingadjustments that move searched items to the top of the tree. The conjecture,called dynamic optimality, is that the cost of splaying is always within aconstant factor of the optimal algorithm for performing searches. We lay afoundation for proving the dynamic optimality conjecture. Central to our methodis approximate monotonicity. Approximately monotone algorithms are those whosecost does not increase by more than a fixed multiple after removing searchesfrom the sequence. As we shall see, Splay is dynamically optimal if and only ifit is approximately monotone. This result extends to a weaker form ofapproximate monotonicity as well as insertion, deletion, and relatedalgorithms. We prove that a lower bound on optimal execution cost isapproximately monotone and outline how to adapt this proof from the lower boundto Splay, and how to overcome the remaining barriers to establishing dynamicoptimality.

A Foundation for Proving Splay is Dynamically Optimal