On the longest increasing subsequence of a circular list
The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time 0(n(3/2) log n) and storage requirement 0(n). It is proved that the expected length mu(n) of the LICS satisfies lim(n ->infinity) mu(n)/2 root = 1. Numerical experiments with the algorithm suggest that vertical bar mu(n) - 2 root n vertical bar = O(n(1/6)). (c) 2006 Elsevier B.V. All rights reserved.
combinatorial problems randomized algorithms