Randomized algorithm for the sum selection problem

Abstract: Let be a sequence of real numbers . We consider the Sum Selection Problem as that of finding the segment such that the rank of over all possible feasible segments is , where a feasible segment is a consecutive subsequence of , and its width satisfies for some given integers and , and . It is a generalization of two well-known problems: the Selection Problem in computer science for which , and the Maximum Sum Segment Problem in bioinformatics for which the rank is the total number of possible feasible segments. We will give a randomized algorithm for the Sum Selection Problem that runs in expected time. It matches the optimal time randomized algorithm for the Selection Problem. We can also solve the k Maximum Sums Problem, to enumerate the largest sums, in expected time. The previously best known result was an algorithm that solves this problem for the case when , and runs in time in the worst case. [Copyright &y& Elsevier]