×

Improved algorithms for the \(k\) maximum-sums problems. (English) Zbl 1155.68604

Given a sequence of n real numbers and an integer \(k\), \(1\leq k\leq n(n-1)/2\), the \(k\) maximum-sum segments problem is to locate the \(k\) segments whose sums are the \(k\) largest among all possible segment sums. Recently, F. Bengtsson and J. Chen [Lect. Notes Comput. Sci. 3341, 137–148 (2004; Zbl 1100.68643), Algorithmica 46, No. 1, 27–41 (2006; Zbl 1100.68124)] gave an \(O(\min{k+nlog^2n,n\sqrt{k}})\)-time algorithm for this problem. S. E. Bae and T. Takaoka later proposed a more efficient algorithm for small \(k\). In this paper, we propose an \(O(n+k\log(\min\{n,k\}))\)-time algorithm for the same problem, which is superior to both of them when \(k\) is \(o(n \log n)\). We also give the first optimal algorithm for delivering the \(k\) maximum-sum segments in non-decreasing order if \(k\leq n\). Then we develop an \(O(n^{2d-1}+k\log(\min\{n,k\}))\)-time algorithm for the \(d\)-dimensional version of the problem, where \(d>1\) and each dimension, without loss of generality, is of the same size \(n\). This improves the best previously known \(O(n^{2d-1}C)\)-time algorithm, also by Bengtsson and Chen, where \(C=\min \{k+n\log^2n, n\sqrt{k}\}\). It should be pointed out that, given a two-dimensional array of size \(m\times n\), our algorithm for finding the \(k\) maximum-sum subarrays is the first one achieving cubic time provided that \(k\) is \(O(m^2n/\log n)\).

MSC:

68W40 Analysis of algorithms

Software:

SEGID; MAVG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allison, L., Longest biased interval and longest non-negative sum interval, Bioinformatics, 19, 1294-1295 (2003)
[2] S.E. Bae, T. Takaoka, Algorithms for the Problem of \(kk\); S.E. Bae, T. Takaoka, Algorithms for the Problem of \(kk\)
[3] Bae, S. E.; Takaoka, T., Improved Algorithms for the \(K\)-Maximum Subarray Problem for Small \(K\), (Proc. 11th Annual Internat. Computing and Combinatorics Conference (2005)), 621-631 · Zbl 1128.68563
[4] F. Bengtsson, J. Chen, Efficient algorithms for \(k\); F. Bengtsson, J. Chen, Efficient algorithms for \(k\) · Zbl 1100.68643
[5] Bentley, J., Programming pearls: algorithm design techniques, Commun. ACM, 865-871 (1984)
[6] Bentley, J., Programming pearls: perspective on performance, Commun. ACM, 1087-1092 (1984)
[7] K.-Y. Chen, K.-M Chao, On the range maximum-sum segment query problem, in: Proc. 15th Internat. Symp. Algorithms and Computation, Lecture Notes in Computer Science, Vol. 3341, 2004, pp. 294-305.; K.-Y. Chen, K.-M Chao, On the range maximum-sum segment query problem, in: Proc. 15th Internat. Symp. Algorithms and Computation, Lecture Notes in Computer Science, Vol. 3341, 2004, pp. 294-305. · Zbl 1116.68669
[8] Chen, K.-Y.; Chao, K.-M., Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint, Inform. Process. Lett., 96, 197-201 (2005) · Zbl 1184.68208
[9] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, second ed., The MIT Press, Cambridge, 1999, pp. 185-196.; T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, second ed., The MIT Press, Cambridge, 1999, pp. 185-196.
[10] T.-H. Fan, S. Lee, H.-I. Lu, T.-S. Tsou, T.-C. Wang, A. Yao, An optimal algorithm for maximum-sum segment and its application in bioinformatics, in: Proc. Eighth Internat. Conf. on Implementation and Application of Automata, Lecture Notes in Computer Science, Vol. 2759, 2003, pp. 251-257.; T.-H. Fan, S. Lee, H.-I. Lu, T.-S. Tsou, T.-C. Wang, A. Yao, An optimal algorithm for maximum-sum segment and its application in bioinformatics, in: Proc. Eighth Internat. Conf. on Implementation and Application of Automata, Lecture Notes in Computer Science, Vol. 2759, 2003, pp. 251-257. · Zbl 1279.92064
[11] Fukuda, T.; Morimoto, Y.; Morishita, S.; Tokuyama, T., Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, (Proc. 1996 ACM SIGMOD Internat. Conf. on Management of Data (1996)), 13-23
[12] Grenander, U., Pattern Analysis (1978), Springer: Springer New York · Zbl 0428.68098
[13] Huang, X., An algorithm for identifying regions of a DNA sequence that satisfy a content requirement, Comput. Appl. Biosci., 10, 219-225 (1994)
[14] T.-C. Lin, D.T. Lee, Randomized algorithm for the sum selection problem, in: Proc. 16th Internat. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 3827, 2005, pp. 515-523.; T.-C. Lin, D.T. Lee, Randomized algorithm for the sum selection problem, in: Proc. 16th Internat. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 3827, 2005, pp. 515-523. · Zbl 1173.68855
[15] Lin, Y.-L.; Huang, X.; Jiang, T.; Chao, K.-M., MAVG: locating non-overlapping maximum average segments in a given sequence, Bioinformatics, 19, 151-152 (2003)
[16] Lin, Y.-L.; Jiang, T.; Chao, K.-M., Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis, J. Comput. System Sci., 65, 570-586 (2002) · Zbl 1059.68024
[17] Perumalla, K.; Deo, N., Parallel algorithms for maximum subsequence and maximum subarray, Parallel Process. Lett., 5, 367-373 (1995)
[18] Ruzzo, W. L.; Tompa, M., A linear time algorithm for finding all maximal scoring subsequences, (Proc. Seventh Internat. Conf. on Intelligent Systems for Molecular Biology (1999)), 234-241
[19] Takaoka, T., Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, (Electronic Notes in Theoretical Computer Science, Vol. 61 (2002)), 1-10
[20] Tamaki, T.; Tokuyama, T., Algorithms for the maximum subarray problem based on matrix multiplication, (Proc. Ninth Annu. ACM-SIAM Symp. on Discrete Algorithms (1998)), 446-452 · Zbl 0942.68143
[21] Wang, L.; Xu, Y., SEGID: identifying interesting segments in (multiple) sequence alignments, Bioinformatics, 19, 297-298 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.