Improved algorithms for the k maximum-sums problems
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, \textit{F. Bengtsson} and \textit{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)\).
- Algorithms and Computation
- Algorithms and Computation
- Algorithms and Computation
- An optimal algorithm for maximum-sum segment and its application in bioinformatics (extended abstract)
- Computing and Combinatorics
- Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
- scientific article; zbMATH DE number 1303586 (Why is no real title available?)
- Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint
- Pattern analysis. Lectures in pattern theory. Vol. II
- Efficient algorithms for the maximum sum problems
- Robust optimization in the presence of uncertainty: a generic approach
- Efficient algorithms for the sum selection problem and \(k\) maximum sums problem
- Efficient algorithms for \(k\) maximum sums
- Calculational developments of new parallel algorithms for size-constrained maximum-sum segment problems
- ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS
- A Linear Time Algorithm for the k Maximal Sums Problem
- scientific article; zbMATH DE number 6146456 (Why is no real title available?)
- Algorithms and Computation
- Computing and Combinatorics
- Algorithms and Computation
- Randomized algorithm for the sum selection problem
- Ranking \(k\) maximum sums
- Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
- Optimal algorithms for the average-constrained maximum-sum segment problem
This page was built for publication: Improved algorithms for the \(k\) maximum-sums problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2508973)
