Fully dynamic approximation of LIS in polylogarithmic time
Paweł Gawrychowski, Wojciech Janczewski · 2021
We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an array. In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/є)O(1/є))-approximation of LIS under both operations with worst-case update time Õ(nє), for any constant є>0 (Õ hides factors polynomial in logn, where n is the length of the input). We exponentially improve on their result by designing an algorithm that maintains an (1+є) approximation of LIS under both operations with worst-case update time Õ(є−5). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.