A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence

This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let $n$ be the input size and $k$ be the LIS length of the input. Sequentially, LIS is a simple textbook problem that can be solved using dynamic programming (DP) in $O(n\log n)$ work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal $O(n\log n)$ work and non-trivial parallelism (i.e., $\tilde{O}(k)$ or $o(n)$ span). Here, the work of a parallel algorithm is the total number of operations, and the span is the longest dependent instructions. This paper proposes a parallel LIS algorithm that costs $O(n\log k)$ work, $\tilde{O}(k)$ span, and $O(n)$ space, and is \emph{much simpler} than the previous parallel LIS algorithms. We also generalize the algorithm to a weighted version of LIS, which maximizes the weighted sum for all objects in an increasing subsequence. Our weighted LIS algorithm has $O(n\log^2 n)$ work and $\tilde{O}(k)$ span. We also implemented our parallel LIS algorithms. Due to simplicity, our implementation is light-weighted, efficient, and scalable. On input size $10^9$, our LIS algorithm outperforms a highly-optimized sequential algorithm (with $O(n\log k)$ cost) on inputs with $k\le 3\times 10^5$. Our algorithm is also much faster than the best existing parallel implementation by Shen et al. on all input instances.