The dynamic optimality conjecture
Are splay trees within a constant factor of the best possible binary search tree, on every access sequence?
Inferred from the community field; finer classification has not been reviewed.
Problem statement
Conjecture: for every access sequence , the total cost of serving with a splay tree is , where is the cost of the optimal offline dynamic binary search tree for .
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Sleator and Tarjan posed the conjecture in the 1985 paper that introduced splay trees. It is unusual in that the benchmark is an offline optimum that is itself not known to be computable in polynomial time.
Known partial results
- Splay trees are known to satisfy the static optimality, static finger, working set and dynamic finger properties — every consequence of dynamic optimality that has been isolated so far.
- Tango trees (Demaine, Harmon, Iacono, Pătraşcu) are -competitive, which is the best proven competitive ratio for any BST algorithm.
- Whether can be computed or approximated in polynomial time is itself open.
- The related Greedy BST algorithm is conjectured to be dynamically optimal too, and is equivalent to a clean geometric problem about point sets.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.