Greedy is an almost optimal deque

Parinya Chalermsook, Mayank Goswami, László Kozma*, Kurt Mehlhorn, Thatchaphol Saranurak

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Pătraşcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online GREEDY BST algorithm introduced by DHIKP. GREEDY BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of GREEDY BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that GREEDY BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Ω(log |U| + n) on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Ω(n log n) with high probability. Besides the splay tree noted before, GREEDY BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing GREEDY BST. Our work is intended as a step towards a full understanding of GREEDY BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
PublisherSpringer Verlag
Pages152-165
Number of pages14
Volume9214
ISBN (Print)9783319218397
DOIs
Publication statusPublished - 2015
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Algorithms and Data Structures - Victoria, Canada
Duration: 5 Aug 20157 Aug 2015
Conference number: 14

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9214
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceInternational Symposium on Algorithms and Data Structures
Abbreviated titleWADS
CountryCanada
CityVictoria
Period05/08/201507/08/2015

Fingerprint Dive into the research topics of 'Greedy is an almost optimal deque'. Together they form a unique fingerprint.

Cite this