Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence
Journal
Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
Part Of
Annual ACM Symposium on Parallelism in Algorithms and Architectures
Start Page
249
End Page
259
ISBN (of the container)
978-145039545-8
Date Issued
2023-06-17
Author(s)
Abstract
The paper presents parallel algorithms for multiplying implicit simple unit-Monge matrices (Krusche and Tiskin, PPAM 2009) of size n x n in the EREW PRAM model. We show implicit simple unit-Monge matrices multiplication of size n x n can be achieved by a deterministic EREW PRAM algorithm with O(n log n log log n) total work and O(log3 n) span. This implies that there is a deterministic EREW PRAM algorithm solving the longest increasing subsequence (LIS) problem in O(n log2 n log log n) work and O(log 4 n) span. Furthermore, with randomization and bitwise operations, implicitly multiplying two simple unit-Monge matrices can be improved to O(n log n) work and O(log3n) span, which leads to a randomized EREW PRAM algorithm obtaining LIS in O(nlog2n) work and O(log4n) span with high probability. In the regime where the LIS has length k = Ψ(log3n), our results improve the span from Õ(n2/3) (Krusche and Tiskin, SPAA 2010) and O(klog n) (Gu, Men, Shen, Sun, and Wan, SPAA 2023) to O(log4 n) while the total work remains near optimal Õ (n).
Event(s)
5th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023
Publisher
ACM
Type
conference paper