1. Efficient algorithms for the sum selection problem and maximum sums problem
- Author
-
Lin, Tien-Ching and Lee, D.T.
- Subjects
- *
ALGORITHMS , *MAXIMUM principles (Mathematics) , *RANKING (Statistics) , *MATHEMATICAL sequences , *REAL numbers , *STOCHASTIC processes - Abstract
Abstract: Given a sequence of real numbers and a positive integer , the Sum Selection Problem is to find the segment such that the rank of the sum is over all segments. We present a deterministic algorithm for this problem that runs in time. The previously best known result for this problem is a randomized algorithm that runs in expected time. Applying this algorithm we can obtain a deterministic algorithm for the k Maximum Sums Problem, i.e., the problem of enumerating the largest sum segments, that runs in time. The previously best known randomized and deterministic algorithms for the k Maximum Sums Problem run respectively in expected time and in worst case time. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF