Optimal Randomized Algorithm for the Density Selection Problem

Abstract. In the paper we consider a generalized version of three well-known problems: Selection Problem in computer science, Slope Se-lection Problem in computational geometry and Maximum-Density Segment Problem in bioinformatics. Given a sequence A = (a1, w1), (a2, w2),..., (an, wn) of n ordered pairs (ai, wi) of real numbers ai and wi> 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(n2) consecutive subse-quences A(i, j) satisfying width constraint ≤ w(i, j) = ∑jt=i wt ≤ u such that the rank of its density d(i∗, j∗) = ∑j∗ t=i ∗ at/w(i ∗, j∗) is k. We will give a randomized algorithm for density selection problem that runs in optimal expected O(n log n) time.