2026-07-20T11:57:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8491 2024-03-06T10:42:21Z ddc:004 open_access

Space-Efficient Algorithms for Longest Increasing Subsequence Kiyomi, Masashi Ono, Hirotaka Otachi, Yota Schweitzer, Pascal Tarui, Jun longest increasing subsequence patience sorting space-efficient algorithm Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For sqrt(n) <= s <= n, we present algorithms that use O(s log n) bits and O(1/s n^2 log n) time for computing the length of a longest increasing subsequence, and O(1/s n^2 log^2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Masashi Kiyomi and Hirotaka Ono and Yota Otachi and Pascal Schweitzer and Jun Tarui 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.44 urn:nbn:de:0030-drops-84911 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.44 eng https://creativecommons.org/licenses/by/3.0/legalcode