Computing a longest increasing subsequence of length k in time O(n\log\log k)

Maxime Crochemore (1) , Ely Porat (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Computer Science [Bar Ilan]

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.

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, Ely Porat. Computing a longest increasing subsequence of length k in time O(n\log\log k). Visions of computer science, 2008, Swindon, UK, United Kingdom. pp.69-74. ⟨hal-00620279⟩