Document Open Access Logo

Space-Efficient Algorithms for Longest Increasing Subsequence

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

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.44.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Masashi Kiyomi
Hirotaka Ono
Yota Otachi
Pascal Schweitzer
Jun Tarui

Cite As Get BibTex

Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, and Jun Tarui. Space-Efficient Algorithms for Longest Increasing Subsequence. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.44

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.

Subject Classification

Keywords
  • longest increasing subsequence
  • patience sorting
  • space-efficient algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hee-Kap Ahn, Nicola Baraldo, Eunjin Oh, and Francesco Silvestri. A time-space trade-off for triangulations of points in the plane. In Yixin Cao and Jianer Chen, editors, Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, volume 10392 of Lecture Notes in Computer Science, pages 3-12. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62389-4_1.
  2. David Aldous and Persi Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bulletin of the American Mathematical Society, 36(4):413-432, 1999. URL: http://dx.doi.org/10.1090/S0273-0979-99-00796-X.
  3. Tetsuo Asano, Amr Elmasry, and Jyrki Katajainen. Priority queues and sorting for read-only data. In T.-H. Hubert Chan, Lap Chi Lau, and Luca Trevisan, editors, Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings, volume 7876 of Lecture Notes in Computer Science, pages 32-41. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38236-9_4.
  4. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search using o(n) bits. In Hee-Kap Ahn and Chan-Su Shin, editors, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, volume 8889 of Lecture Notes in Computer Science, pages 553-564. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_44.
  5. Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Improved time-space trade-offs for computing voronoi diagrams. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.9.
  6. Sergei Bespamyatnikh and Michael Segal. Enumerating longest increasing subsequences and patience sorting. Inf. Process. Lett., 76(1-2):7-11, 2000. URL: http://dx.doi.org/10.1016/S0020-0190(00)00124-1.
  7. Allan Borodin and Stephen A. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput., 11(2):287-297, 1982. URL: http://dx.doi.org/10.1137/0211022.
  8. Alexander Burstein and Isaiah Lankham. Combinatorics of patience sorting piles. Séminaire Lotharingien de Combinatoire, 54A:B54Ab, 2006. URL: http://www.mat.univie.ac.at/~slc/wpapers/s54Aburlank.html.
  9. Sankardeep Chakraborty and Srinivasa Rao Satti. Space-efficient algorithms for maximum cardinality search, stack bfs, queue BFS and applications. In Yixin Cao and Jianer Chen, editors, Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, volume 10392 of Lecture Notes in Computer Science, pages 87-98. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62389-4_8.
  10. Timothy M. Chan and Eric Y. Chen. Multi-pass geometric algorithms. Discrete & Computational Geometry, 37(1):79-102, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1275-6.
  11. Stephen A. Cook. Deterministic cfl’s are accepted simultaneously in polynomial time and log squared space. In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 338-345. ACM, 1979. URL: http://dx.doi.org/10.1145/800135.804426.
  12. Maxime Crochemore and Ely Porat. Fast computation of a longest increasing subsequence and application. Inf. Comput., 208(9):1054-1059, 2010. URL: http://dx.doi.org/10.1016/j.ic.2010.04.003.
  13. Omar Darwish and Amr Elmasry. Optimal time-space tradeoff for the 2d convex-hull problem. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 284-295. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_24.
  14. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient basic graph algorithms. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 288-301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  15. Funda Ergün and Hossein Jowhari. On the monotonicity of a data stream. Combinatorica, 35(6):641-653, 2015. URL: http://dx.doi.org/10.1007/s00493-014-3035-1.
  16. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci., 34(1):19-26, 1987. URL: http://dx.doi.org/10.1016/0022-0000(87)90002-X.
  17. Michael L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. URL: http://dx.doi.org/10.1016/0012-365X(75)90103-X.
  18. Anna Gál and Parikshit Gopalan. Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence. SIAM J. Comput., 39(8):3463-3479, 2010. URL: http://dx.doi.org/10.1137/090770801.
  19. Parikshit Gopalan, T.S. Jayram, Robert Krauthgamer, and Ravi Kumar. Estimating the sortedness of a data stream. In SODA 2007, pages 318-327, 2007. URL: http://dl.acm.org/citation.cfm?id=1283417.
  20. James W. Hunt and Thomas G. Szymanski. A fast algorithm for computing longest subsequences. Commun. ACM, 20(5):350-353, 1977. URL: http://dx.doi.org/10.1145/359581.359603.
  21. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  22. David Liben-Nowell, Erik Vee, and An Zhu. Finding longest increasing and common subsequences in streaming data. J. Comb. Optim., 11(2):155-175, 2006. URL: http://dx.doi.org/10.1007/s10878-006-7125-x.
  23. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic time-space trade-offs for k-sum. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 58:1-58:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.58.
  24. C. L. Mallows. Problem 62-2, patience sorting. SIAM Review, 4(2):143-149, 1962. URL: http://www.jstor.org/stable/2028371.
  25. C. L. Mallows. Problem 62-2. SIAM Review, 5(4):375-376, 1963. URL: http://www.jstor.org/stable/2028347.
  26. C. L. Mallows. Patience sorting. Bulletin of the Institute of Mathematics and its Applications, 9:216-224, 1973. Google Scholar
  27. J. Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12:315-323, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90061-4.
  28. Timothy Naumovitz and Michael E. Saks. A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1252-1262. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.83.
  29. Noam Nisan. RL ⊆ SC. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 619-623. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129772.
  30. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 264-268. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743455.
  31. Michal Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 57:1-57:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.57.
  32. Prakash Ramanan. Tight Ω(n lg n) lower bound for finding a longest increasing subsequence. International Journal of Computer Mathematics, 65(3-4):161-164, 1997. URL: http://dx.doi.org/10.1080/00207169708804607.
  33. Dan Romik. The surprising mathematics of longest increasing subsequences. Cambridge University Press, 2015. URL: http://dx.doi.org/10.1017/CBO9781139872003.
  34. Michael E. Saks and C. Seshadhri. Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1698-1709. SIAM, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.122.
  35. Michael E. Saks and C. Seshadhri. Estimating the longest increasing sequence in polylogarithmic time. SIAM J. Comput., 46(2):774-823, 2017. URL: http://dx.doi.org/10.1137/130942152.
  36. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. URL: http://dx.doi.org/10.1016/S0022-0000(70)80006-X.
  37. Craige Schensted. Longest increasing and decreasing subsequences. Canadian Journal of Mathematics, 13(2):179-191, 1961. URL: http://dx.doi.org/10.4153/CJM-1961-015-3.
  38. Xiaoming Sun and David P. Woodruff. The communication and streaming complexity of computing the longest common and increasing subsequences. In SODA 2007, pages 336-345, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283419.
  39. Joshua R. Wang. Space-efficient randomized algorithms for K-SUM. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 810-829. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_67.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact