论文标题
LIS在聚类时间中的完全动态近似
Fully Dynamic Approximation of LIS in Polylogarithmic Time
论文作者
论文摘要
我们重新审查了（i）插入元素的数组中维持最长增加的子序列（LI）的问题，以及（ii）删除数组的元素。在最近的突破中，Mitzenmacher和Seddighin [STOC 2020]设计了一种算法，该算法维持$ \ Mathcal {O}（（1/ε）^{\ Mathcal {\ Mathcal {o}（O}（1/ε）}）$在两种操作中都具有较差的casase Upertation $ nipertia o}（n^ε）$，对于任何常数$ε> 0 $。我们通过设计一种在这两个操作下保持LIS $（1+ε）$近似的算法来呈指数级改进的结果。我们没有使用Mitzenmacher和Seddighin引入的网格包装技术，而是在一种可能具有独立兴趣的新工具上采用了另一种方法：LIS稀疏。 我们结果的一个特别有趣的结果是改进了所谓的Erdős-Szekeres分区的解决方案，在其中，我们寻求$ \ {1,2，\ ldots，n \} $的给定排列划分到$ \ MATHCAL {O}（\ sqrt {n} n} {n} {n}）$ monotences。这个问题反复说为自然示例之一，在这种例子中，我们看到决策树复杂性和算法复杂性之间存在很大的差距。 Mitzenmacher和Seddighin的结果意味着对于此问题，对于任何$ε> 0 $，$ \ MATHCAL {o}（n^{1+ε}）$时间解决方案。我们的算法（实际上，其简单的减少版本）将其进一步改善为$ \ Mathcal {\ tilde o}（n）$。
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 $\mathcal{O}((1/ε)^{\mathcal{O}(1/ε)})$-approximation of LIS under both operations with worst-case update time $\mathcal{\tilde O}(n^ε)$, for any constant $ε>0$. 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 $\mathcal{\tilde O}(ε^{-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. A particularly interesting consequence of our result is an improved solution for the so-called Erdős-Szekeres partitioning, in which we seek a partition of a given permutation of $\{1,2,\ldots,n\}$ into $\mathcal{O}(\sqrt{n})$ monotone subsequences. This problem has been repeatedly stated as one of the natural examples in which we see a large gap between the decision-tree complexity and algorithmic complexity. The result of Mitzenmacher and Seddighin implies an $\mathcal{O}(n^{1+ε})$ time solution for this problem, for any $ε>0$. Our algorithm (in fact, its simpler decremental version) further improves this to $\mathcal{\tilde O}(n)$.
