Projects per year
Abstract
We consider the problem of comparisonsorting an npermutation S that avoids some kpermutation π. Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak [CGK^{+}15b] prove that when S is sorted by inserting the elements into the GreedyFuture [DHI^{+}09] binary search tree, the running time is linear in the extremal function Ex(Pπ ☉ (_{•}^{•}_{•}), n). This is the maximum number of 1s in an n * n 01 matrix avoiding Pπ ☉ (_{•}^{•}_{•}), where Pπ is the k * k permutation matrix of π, and Pπ ☉ (_{•}^{•}_{•}) is the 2k * 3k Kronecker product of Pπ and the “hat” pattern (_{•}^{•}_{•}). The same time bound can be achieved by sorting S with Kozma and Saranurak's SmoothHeap [KS20]. Applying offtheshelf results on the extremal functions of 01 matrices, it was known that Ex(Pπ ☉ (_{•}^{•}_{•}), n) = { Ω ( n · 2α^{(n)}),/O( n · 2α^{(n))3k/2O(1)}) where α(n) is the inverseAckermann function. In this paper we give nearly tight upper and lower bounds on the density of Pπ ☉ (_{•}^{•}_{•}) free matrices in terms of “n”, and improve the dependence on “k” from doubly exponential to singly exponential. Ex(Pπ ☉ (_{•}^{•}_{•}), n) = { Ω ( n · 2α^{(n)}), for most π,/O ( n · 2O^{(k2)+(1+o(1))α(n)}), for all π. As a consequence, sorting πfree sequences can be performed in O(n2^{(1+o(1))α(n)}) time. For many corollaries of the dynamic optimality conjecture, the best analysis uses forbidden 01 matrix theory. Our analysis may be useful in analyzing other classes of access sequences on binary search trees.
Original language  English 

Title of host publication  Proceedings of the 2024 Annual ACMSIAM Symposium on Discrete Algorithms (SODA) 
Editors  David P. Woodruff 
Publisher  Society for Industrial and Applied Mathematics 
Pages  133149 
Number of pages  17 
ISBN (Electronic)  9781611977912 
DOIs  
Publication status  Published  2024 
MoE publication type  A4 Conference publication 
Event  ACMSIAM Symposium on Discrete Algorithms  Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 Conference number: 35 
Conference
Conference  ACMSIAM Symposium on Discrete Algorithms 

Abbreviated title  SODA 
Country/Territory  United States 
City  Alexandria 
Period  07/01/2024 → 10/01/2024 
Fingerprint
Dive into the research topics of 'Sorting PatternAvoiding Permutations via 01 Matrices Forbidding Product Patterns'. Together they form a unique fingerprint.Projects
 1 Finished

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P. (Principal investigator), Jindal, G. (Project Member), Franck, M. (Project Member), Khodamoradi, K. (Project Member), Yingchareonthawornchai, S. (Project Member), Gadekar, A. (Project Member), Orgo, L. (Project Member), Jiamjitrak, W. (Project Member) & Spoerhase, J. (Project Member)
01/02/2018 → 31/01/2024
Project: EU: ERC grants