Space-efficient algorithms for longest increasing subsequence

DOI10.4230/LIPICS.STACS.2018.44MaRDI QIDQ3304143zbMATH OpenOpenAlexFDO

Authors Masashi Kiyomi, Hirotaka Ono, Yota Otachi, P. Schweitzer, Jun Tarui

Publication date 5 August 2020

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

zbMATH Keywords

longest increasing subsequencepatience sortingspace-efficient algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Calculation of integer sequences (11Y55) Searching and sorting (68P10) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Abstract: 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(nlogn)$ time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For $sqrtnleslen$, we present algorithms that use $O(slogn)$ bits and $O(frac1scdot{n}^{2}cdotlogn)$ time for computing the length of a longest increasing subsequence, and $O(frac1scdot{n}^{2}cdotlo{g}^{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.

Recommendations

• Space-efficient algorithms for longest increasing subsequence
• A linear space algorithm for computing a longest common increasing subsequence
• Longest common subsequence in sublinear space
• Fast computation of a longest increasing subsequence and application
• An algorithm for the determination of longest increasing subsequence in a sequence

Cites work

• A fast algorithm for computing longest common subsequences
• A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
• A time-space trade-off for triangulations of points in the plane
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Combinatorics of patience sorting piles
• Communication Complexity
• Depth-First Search Using O(n) Bits
• Deterministic time-space trade-offs for k-SUM
• Enumerating longest increasing subsequences and patience sorting
• Estimating the longest increasing sequence in polylogarithmic time
• Estimating the sortedness of a data stream
• Fast computation of a longest increasing subsequence and application
• Finding longest increasing and common subsequences in streaming data
• Longest Increasing and Decreasing Subsequences
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• Multi-pass geometric algorithms
• On computing the length of longest increasing subsequences
• On space efficiency of algorithms working on structural decompositions of graphs
• On the monotonicity of a data stream
• Optimal time-space tradeoff for the 2D convex-hull problem
• Priority queues and sorting for read-only data
• Relationships between nondeterministic and deterministic tape complexities
• Selection and sorting with limited storage
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• Space-efficient basic graph algorithms
• Space-efficient randomized algorithms for k-sum
• The communication and streaming complexity of computing the longest common and increasing subsequences
• The surprising mathematics of longest increasing subsequences
• Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
• Upper bounds for time-space trade-offs in sorting and selection

Cited in

(5)

• An algorithm for the determination of longest increasing subsequence in a sequence
• Space-efficient algorithms for longest increasing subsequence
• Sequential dependency computation via geometric data structures
• Estimating the longest increasing sequence in polylogarithmic time
• Covers in optimal space

This page was built for publication: Space-efficient algorithms for longest increasing subsequence

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