论文标题
改进的动态算法，以最长增加子序列
Improved Dynamic Algorithms for Longest Increasing Subsequence
论文作者
论文摘要
我们研究了最长增加的子序列（\ textsf {lis}）问题的动态算法。动态\ textsf {lis}算法维护一个序列，但要按以下形式的操作，一个逐一到达的操作：（i）插入元素，（ii）删除元素，或（iii）代替另一个元素。执行每个操作后，算法必须报告当前序列最长增加子序列的长度。 我们的主要贡献是带有sublinear更新时间的第一个精确动态\ textsf {lis}算法。更确切地说，我们提出了一种随机算法，该算法会在时间上执行每个操作$ \ tilde o（n^{2/3}）$，在每个更新后，将答案报告给\ textsf {lis}问题，并以较高的可能性正确地报告了问题。我们对这种算法使用了几种新颖的技术和观察结果，这些算法可能会在未来的工作中找到其应用。 在本文的第二部分中，我们研究了近似动态\ textsf {lis}算法，这些算法可以低估界面乘法因子内的解决方案大小。在这种情况下，我们给出了一个确定性算法，并具有更新时间$ O（n^{o（1）}）$和近似因子$ 1-O（1）$。 Mitzenmacher和Seddighin（stoc'20）的先前工作大大改善了这一结果，该工作呈现出$ω（ε^{o（1/ε）}）$ - 近似算法，并带有更新时间$ \ tilde $ \ tilde o（n^ε）$，以获取任何常量$ε> 0 $。
We study dynamic algorithms for the longest increasing subsequence (\textsf{LIS}) problem. A dynamic \textsf{LIS} algorithm maintains a sequence subject to operations of the following form arriving one by one: (i) insert an element, (ii) delete an element, or (iii) substitute an element for another. After performing each operation, the algorithm must report the length of the longest increasing subsequence of the current sequence. Our main contribution is the first exact dynamic \textsf{LIS} algorithm with sublinear update time. More precisely, we present a randomized algorithm that performs each operation in time $\tilde O(n^{2/3})$ and after each update, reports the answer to the \textsf{LIS} problem correctly with high probability. We use several novel techniques and observations for this algorithm that may find their applications in future work. In the second part of the paper, we study approximate dynamic \textsf{LIS} algorithms, which are allowed to underestimate the solution size within a bounded multiplicative factor. In this setting, we give a deterministic algorithm with update time $O(n^{o(1)})$ and approximation factor $1-o(1)$. This result substantially improves upon the previous work of Mitzenmacher and Seddighin (STOC'20) that presents an $Ω(ε^{O(1/ε)})$-approximation algorithm with update time $\tilde O(n^ε)$ for any constant $ε> 0$.
