6

[2211.04112] Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomp...

 2 years ago
source link: https://arxiv.org/abs/2211.04112
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

[Submitted on 8 Nov 2022]

Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition

Download PDF

Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i.e., starting with any initial tree, their access costs on any sequence is conjectured to be within O(1) factor of the offline optimal. However, in the past four decades, the question has remained elusive even for highly restricted input.
In this paper, we prove new bounds on the cost of Greedy in the ''pattern avoidance'' regime. Our new results include:
The (preorder) traversal conjecture for Greedy holds up to a factor of O(2^{\alpha(n)}), improving upon the bound of 2^{\alpha(n)^{O(1)}} in (Chalermsook et al., FOCS 2015). This is the best known bound obtained by any online BSTs.
We settle the postorder traversal conjecture for Greedy.
The deque conjecture for Greedy holds up to a factor of O(\alpha(n)), improving upon the bound 2^{O(\alpha(n))} in (Chalermsook, et al., WADS 2015).
The split conjecture holds for Greedy up to a factor of O(2^{\alpha(n)}).
Key to all these results is to partition (based on the input structures) the execution log of Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be leveraged. Finally, we show the applicability of this technique to handle a class of increasingly complex pattern-avoiding input sequences, called k-increasing sequences.
As a bonus, we discover a new class of permutation matrices whose extremal bounds are polynomially bounded. This gives a partial progress on an open question by Jacob Fox (2013).

Comments: Accepted to SODA 2023
Subjects: Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2211.04112 [cs.DS]
  (or arXiv:2211.04112v1 [cs.DS] for this version)
  https://doi.org/10.48550/arXiv.2211.04112

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK