We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Efficient Algorithms for the Maximum Sum Problems.
- Authors
Sung Eun Bae; Tong-Wook Shinn; Tadao Takaoka
- Abstract
We present efficient sequential and parallel algorithms for the maximum sum (MS) problem, which is to maximize the sum of some shape in the data array. We deal with two MS problems; the maximum subarray (MSA) problem and the maximum convex sum (MCS) problem. In the MSA problem, we find a rectangular part within the given data array that maximizes the sum in it. The MCS problem is to find a convex shape rather than a rectangular shape that maximizes the sum. Thus, MCS is a generalization of MSA. For the MSA problem, O(n) time parallel algorithms are already known on an (n, n) 2D array of processors. We improve the communication steps from 2n -1 to n, which is optimal. For the MCS problem, we achieve the asymptotic time bound of O(n) on an (n, n) 2D array of processors. We provide rigorous proofs for the correctness of our parallel algorithm based on Hoare logic and also provide some experimental results of our algorithm that are gathered from the Blue Gene/P super computer. Furthermore, we briefly describe how to compute the actual shape of the maximum convex sum.
- Subjects
PARALLEL algorithms; HOARE logic; ARRAY processing; ARRAY processors; ALGORITHMS
- Publication
Algorithms, 2017, Vol 10, Issue 1, p5
- ISSN
1999-4893
- Publication type
Article
- DOI
10.3390/a10010005