Improved dynamic algorithms for longest increasing subsequence

DOI10.1145/3406325.3451026MaRDI QIDQ6087033zbMATH OpenFDO

Authors Tomasz Kociumaka, S. Seddighin

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10874

zbMATH Keywords

dynamic algorithmslongest increasing subsequence

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study dynamic algorithms for the longest increasing subsequence ( extsf{LIS}) problem. A dynamic extsf{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 extsf{LIS} algorithm with sublinear update time. More precisely, we present a randomized algorithm that performs each operation in time $ildeO(n^{2/3})$ and after each update, reports the answer to the extsf{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 extsf{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 $Omega(epsilo{n}^{O(1/epsilon)})$-approximation algorithm with update time $ildeO(n^{e}psilon)$ for any constant $epsilon>0$.

Cited in

(4)

• An algorithm for the determination of longest increasing subsequence in a sequence
• Streaming and query once space complexity of longest increasing subsequence
• Approximation algorithms for LCS and LIS with truly improved running times
• Core-sparse Monge matrix multiplication: improved algorithm and applications

This page was built for publication: Improved dynamic algorithms for longest increasing subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087033)