Computing a Longest Increasing Subsequence of Length k in Time O(n log log k)

Abstract

We consider the complexity of computing a longest increasing subsequence parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, . . . , n} can be computed in time O( n log log k) in the RAM model, improving the previous 30-year bound of O( n log log n). The optimality of the new bound is an open question.

Affiliations

King’s College London, Strand, London WC2R 2LS, UK

and Université Paris-Est.

Bar-Ilan University, Ramat-Gan 52900, Israel

Contributors

MAXIME CROCHEMORE

ELY PORAT

Conference

Publication date: September 2008

Publication date (Print): September 2008

Pages: 69-74

ID: 10.14236/ewic/VOCS2008.7

Copyright statement: © MAXIME CROCHEMORE et al. Published by BCS Learning and Development Ltd. Visions of Computer Science - BCS International Academic Conference

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Visions of Computer Science - BCS International Academic Conference

Conference acronym: VOCS

Conference number:

Conference location: Imperial College, London, UK

Conference date: 22 - 24 September 2008

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: BCS International Academic Conference

Product

Product Information: 1477-9358 BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/VOCS2008.7

Self URI (journal page): https://ewic.bcs.org/

Categories

Series title: Electronic Workshops in Computing