Oberseminar
Hauke Reddmann University of Hamburg
May 07, 2021, 12:00, zoom: https://uni-hamburg.zoom.us/j/94889228942
Title: On the geometric equivalent of instance optimalbinary search tree algorithms
A long standing problem on the area of binary search trees (BSTs) isthe Sleator-Tarjan conjecture: Consider the well-known Splay tree. Does it need at most a constant factor γ of the optimal tree algorithm cost for any instance (instance optimality)? This property is known as γ-competitiveness in the framework of Competitive Analysis.
A seminal paper by Demaine a decade ago showed that BST algorithms may be translated to generating anarborally satisfied (AS) superset of a point set defined via the search query, the optimum corresponding to the smallest superset possible. Two points of a setare in AS if their axis-parallel induced rectangle is flat or contains another point of this set, and a point set is in AS if all point pairs are.
Demaine also showed that the general formulation is NP-complete, and rephrased the long known approximation algorithm Greedy Future(GG) into the above geometric setting. In this talk, an introduction to the theme complex will be given. The accompanying Master thesis is based on Demaine’s geometric approach, its main result being the refutation of Kozma’s conjecture γ(GG)≤4/3 by showing γ(GG)≥26/17. Also, for any online algorithm A, γ(A)≥4/3. Some other results are shown too.