Efficient Algorithms for the Maximum Sum Problems

• DOI: 10.3390/a10010005
• Publication Date: 2017-01-04T14:39:32Z
• Authors: Sung Bae; Tong-Wook Shinn; Tadao Takaoka
• Keywords: Subset sum problem

We present efficient sequential and parallel algorithms for the maximum sum (MS) problem, which is to maximize of some shape in data array. deal with two MS problems; subarray (MSA) problem convex (MCS) problem. In MSA we find a rectangular part within given array that maximizes it. The MCS rather than sum. Thus, generalization MSA. For O ( n ) time are already known on an , 2D processors. improve communication steps from 2 − 1 n, optimal. achieve asymptotic bound provide rigorous proofs correctness our algorithm based Hoare logic also experimental results gathered Blue Gene/P super computer. Furthermore, briefly describe how compute actual