Efficient algorithms for the maximum sum problems

DOI10.3390/A10010005MaRDI QIDQ1662587zbMATH OpenOpenAlexFDO

Authors Sung Eun Bae, Tong-Wook Shinn, Tadao Takaoka

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a10010005

zbMATH Keywords

maximum convex summaximum sub-arrayparallel algorithm

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10)

Review text

Summary: 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.

Recommendations

• Efficient algorithms for \(k\) maximum sums
• Algorithms and Computation
• Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem
• Efficient algorithms for the sum selection problem and \(k\) maximum sums problem
• Improved algorithms for the \(k\) maximum-sums problems
• Algorithms and Computation
• Fast parallel algorithms for the maximum sum problem
• Efficient Computation of the Maximum of the Sum of Two Sequences and Applications
• A Linear Time Algorithm for the k Maximal Sums Problem
• Publication:4203809

Cites work

• An axiomatic basis for computer programming
• Data Mining with optimized two-dimensional association rules
• Efficient algorithms for the maximum subarray problem by distance matrix multiplication
• scientific article; zbMATH DE number 1303586 (Why is no real title available?)
• Verifying properties of parallel programs

Cited in

(4)

• Calculational developments of new parallel algorithms for size-constrained maximum-sum segment problems
• Maximizing Range Sum in External Memory
• Algorithms and Computation
• Fast parallel algorithms for the maximum sum problem

This page was built for publication: Efficient algorithms for the maximum sum problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662587)