Space-Efficient Algorithms for Longest Increasing Subsequence

作     者：Kiyomi, Masashi Ono, Hirotaka Otachi, Yota Schweitzer, Pascal Tarui, Jun 

作者机构：Yokohama City Univ Yokohama Kanagawa Japan Nagoya Univ Nagoya Aichi Japan Kumamoto Univ Kumamoto Japan TU Kaiserslautern Kaiserslautern Germany Univ Electrocommun Chofu Tokyo Japan 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2020年第64卷第3期

页      面：522-541页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：Japan Society for the Promotion of Science, JSPS, (18K11168, 18K11169) Japan Society for the Promotion of Science, JSPS 

主　　题：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 mml:mfenced close=) open=(nlogntime and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n = s = n we present algorithms that use O mml:mfenced close=) open=(slogn bits and Omml:mfenced close=) open=(*** for computing the length of a longest increasing subsequence, and O mml:mfenced close=) open=(***2ntime 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.