Helsinki Algorithms Seminar: "An Illustrative Charging Scheme for Dynamic BST" Wanchote Jiamjitrak

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Speaker:
Wanchote Jiamjitrak

Title:
An Illustrative Charging Scheme for Dynamic BST

Abstract:

A 30-year-old famous dynamic optimality conjecture states that "For any sufficiently long search sequence, the cost of splay tree is at most any dynamic binary search tree (BST)". Despite a lot of attention, the conjecture has so far remained out of reach. Indeed, even the most important landmark results only managed to resolve highly restrictive corollaries of the conjecture.

In this talk, we present a new charging scheme inspired by the geometric view of BST algorithm. With our charging scheme, (i) we simplify and give modular proofs for many known consequences of dynamic optimality. (ii) we show that the cost of splay tree is at most that of the move-to-root algorithm. This is a very first instance where the costs of two dynamic trees can be compared directly.

(Joint work with Parinya Chalermsook and Thatchaphol Saranurak.)

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.