Projects per year
Abstract
We consider the problem of comparison-sorting an n-permutation S that avoids some k-permutation π. 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 0-1 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 off-the-shelf results on the extremal functions of 0-1 matrices, it was known that Ex(Pπ ☉ (•••), n) = { Ω ( n · 2α(n)),/O( n · 2α(n))3k/2-O(1)) where α(n) is the inverse-Ackermann 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 0-1 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 ACM-SIAM Symposium on Discrete Algorithms (SODA) |
Editors | David P. Woodruff |
Publisher | Society for Industrial and Applied Mathematics |
Pages | 133-149 |
Number of pages | 17 |
ISBN (Electronic) | 978-1-61197-791-2 |
DOIs | |
Publication status | Published - 2024 |
MoE publication type | A4 Conference publication |
Event | ACM-SIAM Symposium on Discrete Algorithms - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 Conference number: 35 |
Conference
Conference | ACM-SIAM 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 Pattern-Avoiding Permutations via 0-1 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