Optimal Randomized Algorithm for the Density Selection Problem.

In the paper we consider a generalized version of three well-known problems: Selection Problem in computer science, Slope Selection Problem in computational geometry and Maximum-Density Segment Problem in bioinformatics. Given a sequence A = (a₁, w₁),(a₂, w₂) ,..., (a_n, w_n) of n ordered pairs (a_i,w_i) of real numbers a_i and w_i > 0 for each 1 ≤ i ≤ n, two nonnegative real numbers ℓ, u with ℓ ≤ u and a positive integer k, the Density Selection Problem is to find the consecutive subsequence A(i^*,j^*) over all O(n²) consecutive subsequences A(i,j) satisfying width constraint ]> such that the rank of its density ]> is k. We will give a randomized algorithm for density selection problem that runs in optimal expected O(n logn) time. [ABSTRACT FROM AUTHOR]