Efficient algorithms for the sum selection problem and k maximum sums problem
Authors: 
Tien-Ching Lin, D. T. LeeAuthors Info & Claims
Pages 986 - 994
Abstract
Given a sequence of n real numbers A=a"1,a"2,...,a"n and a positive integer k, the Sum Selection Problem is to find the segment A(i^*,j^*)=a"i"^"*,a"i"^"*"+"1,...,a"j"^"* such that the rank of the sum s(i^*,j^*)=@?"t"="i"^"*^j^^^*a"t is k over all n(n-1)2 segments. We present a deterministic algorithm for this problem that runs in O(nlogn) time. The previously best known result for this problem is a randomized algorithm that runs in expected O(nlogn) time. Applying this algorithm we can obtain a deterministic algorithm for the k Maximum Sums Problem, i.e., the problem of enumerating the k largest sum segments, that runs in O(nlogn+k) time. The previously best known randomized and deterministic algorithms for the k Maximum Sums Problem run respectively in expected O(nlogn+k) time and in worst case O(nlog^2n+k) time.
References
[1]
R. Agrawal, T. Imielinski, A. Swami, Data mining using two-dimensional optimized association rules: Scheme, algorithms, and visualization, in: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 1993, pp. 207-216
[2]
Ajtai, M., Komlós, J. and Szemerédi, E., An O(nlogn) sorting networks. Combinatorica. v3. 1-19.
[3]
Alk, S. and Guenther, G., Application of broadcasting with selective reduction to the maximal sum subsegment problem. International Journal of High Speed Computating. v3. 107-119.
[4]
S.E. Bae, T. Takaoka, Algorithms for the problem of k maximum sums and a VLSI algorithm for the k maximum subarrays problem, in: 2004 International Symposium on Parallel Architectures, Algorithms and Networks, 2004, pp. 247-253
[5]
Bae, S.E. and Takaoka, T., Improved algorithms for the k-maximum subarray problem. The Computer Journal. v49 i3. 358-374.
[6]
Bengtsson, F. and Chen, J., Efficient algorithms for k maximum sums. Algorithmica. v46. 27-41.
[7]
Bentley, J., Programming pearls: Algorithm design techniques. Communications of the ACM. v27 i9. 865-873.
[8]
Bentley, J., Programming pearls: Algorithm design techniques. Communications of the ACM. v27 i11. 1087-1092.
[9]
Brönnimannm, H. and Chazelle, B., Optimal slope selection via cuttings. Computational Geometry. v10. 23-29.
[10]
Cheng, C.-H., Chen, K.-Y., Tien, W.-C. and Chao, K.-M., Improved algorithms for the k maximum-sums problems. Theoretical Computer Science. v362. 162-170.
[11]
Cole, R., Salowe, J.S., Steiger, W.L. and Szemeredi, E., An optimal-time algorithm for slope selection. SIAM Journal on Computing. v18 i4. 792-810.
[12]
Cole, R., Slowing down sorign networks to obtain faster sorting algorithm. Journal of the Association for Computing Machinery. v34 i1. 200-208.
[13]
T. Fukuda, Y. Morimoto, S. Morishita, T. Tokuyama, Mining association rules between sets of items in large databases, in: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 1996, pp. 13-23
[14]
Gries, D., A note on the standard strategy for developing loop invariants and loops. Science of Computer Programming. v2. 207-214.
[15]
Lin, T.-C. and Lee, D.T., Randomized algorithm for the sum selection problem. Theoretical Computer Science. v377 i1-3. 151-156.
[16]
Megiddo, N., Applying parallel computation algorithms in the design of serial algorithm. Journal of the Association for Computing Machinery. v30 i4. 852-865.
[17]
Perumalla, K. and Deo, N., Parallel algorithms for maximum subsequence and maximum subarray. Parallel Processing Letters. v5. 367-373.
[18]
K. Qiu, S. Alk, Parallel maximum sum algorithms on interconnection networks, Technical report no. 99-431, Jodrey school of computer science, Acadia University, Canada, 1999
[19]
Smith, D., Applications of a strategy for designing divide-and-conquer algorithms. Science of Computer Programming. v8. 213-229.
[20]
T. Takaoka, Efficient algorithms for the maximum dubarray problem by fistance matrix multiplication, in: Proceedings of the 2002 Australian Theory Symposium, 2002, pp. 189-198
[21]
H. Tamaki, T. Tokuyama, Algorithms for the maximum subarray problem based on matrix multiplication, in: Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms, 1998, pp. 446-452
- Efficient algorithms for the sum selection problem and k maximum sums problem
Recommendations
Efficient algorithms for the sum selection problem and k maximum sums problem
ISAAC'06: Proceedings of the 17th international conference on Algorithms and ComputationGiven a sequence of n real numbers A = a1, a2,..., an and a positive integer k, the Sum Selection Problem is to find the segment A(i,j) = ai , ai+1,..., aj such that the rank of the sum s(i, j) = ∑t=ijat is k over all $\frac{n(n-1)}{2}$ segments. We ...
Randomized algorithm for the sum selection problem
ISAAC'05: Proceedings of the 16th international conference on Algorithms and ComputationGiven a sequence of n real numbers A = a1, a2,..., an and a positive integer k, the Sum Selection Problem is to find the segment A( i,j)=ai, ai+1,..., aj such that the rank of the sum $s(i, j) = \sum_{t = i}^{j}{a_{t}}$ is k over all ${n(n-1)} \over {2}$...
Randomized algorithm for the sum selection problem
Let A be a sequence of n real numbers a"1,a"2,...,a"n. We consider the Sum Selection Problem as that of finding the segment A(i^*,j^*) such that the rank of s(i^*,j^*)=@?"t"="i"^"*^j^^^*a"t over all possible feasible segments is k, where a feasible ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V. © 2009.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 01 February 2010
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025