License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.44
URN: urn:nbn:de:0030-drops-84911
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8491/
Go to the corresponding LIPIcs Volume Portal

Kiyomi, Masashi ; Ono, Hirotaka ; Otachi, Yota ; Schweitzer, Pascal ; Tarui, Jun

Space-Efficient Algorithms for Longest Increasing Subsequence

pdf-format:
LIPIcs-STACS-2018-44.pdf (0.6 MB)

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(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.

BibTeX - Entry

@InProceedings{kiyomi_et_al:LIPIcs:2018:8491,
  author =	{Masashi Kiyomi and Hirotaka Ono and Yota Otachi and Pascal Schweitzer and Jun Tarui},
  title =	{{Space-Efficient Algorithms for Longest Increasing Subsequence}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8491},
  URN =		{urn:nbn:de:0030-drops-84911},
  doi =		{10.4230/LIPIcs.STACS.2018.44},
  annote =	{Keywords: longest increasing subsequence, patience sorting, space-efficient algorithm}
}

Keywords: longest increasing subsequence, patience sorting, space-efficient algorithm
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI