An efficient parallel algorithm for the maximum convex sum problem
Article No.: 23, Pages 1 - 7
Abstract
In this paper, we present a parallel algorithm for the maximum convex sum (MCS) problem, which is a generalization of the maximum subarray (MSA) problem. In the MSA problem, we find a rectangular portion within the given data array that maximizes the sum in it. The MCS problem is to find a convex shape instead of a rectangular shape that maximizes the sum. For the MSA problem, O(n) time parallel algorithms are already known on an (n, n) 2D array of processors. For the MCS problem, we achieve the same 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.
References
[1]
Gordon Bell, Tony Hey and Alex Szalay: Beyond the Data Deluge, Science 323: 1297--1298 (2009)
[2]
John Pavlus: The search for a new machine, Scientific American, 312(5) 48--53 (2015)
[3]
C. E. R. Alves, E. N. Caceres and S. W. Song: BPS/CGM Algorithms for Maximum Subsequence and Maximum Subarray, EuroPVM/MPI 2004, LNCS 3241: 139--146 (2004)
[4]
Jon Louis Bentley: Perspective on Performance. Commun. ACM 27(11): 1087--1092 (1984)
[5]
Sung Eun Bae: Sequential and Parallel Algorithms for Generalized Maximum Subarray Problem. Ph. D thesis. University of Canterbury (2007)
[6]
Sung Eun Bae and Tadao Takaoka: Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem. I-SPAN 2004: 247--253 (2004)
[7]
Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Data Mining with optimized two-dimensional association rules. ACM Trans. Database Syst. 26(2): 179--213 (2001)
[8]
C. A. R. Hoare: An axiomatic basis for computer programming. Communications of the ACM, 12(10):576--580 (1969).
[9]
S. Owicki and D. Gries: Verifying properties of parallel programs: An axiomatic approach. Communications of the ACM, 19(5):279--285 (1976)
[10]
Tadao Takaoka: Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication. Electr. Notes Theor. Comput. Sci. 61: 191--200 (2002)
[11]
Tadao Takaoka: Efficient Parallel Algorithms for the Maximum Subarray Problem. In Proc. Twelfth Australasian Symposium on Parallel and Distributed Computing (AusPDC 2014), Auckland, New Zealand. CRPIT, 152. Javadi, B. and Garg, S. K. Eds., ACS. 45--50 (2014).
[12]
Hisao Tamaki, Takeshi Tokuyama: Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication. SODA 1998: 446--452 (1998)
[13]
IBM: Parallel Environment Runtime Edition for Linux: MPI Programming Guide (SC23-7285-01) (7/2015) http://publib.boulder.ibm.com/epubs/pdf/c2372851.pdf
Recommendations
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryGiven a set Σ of spheres in Ed, with d≥3 and d odd, having a fixed number of m distinct radii ρ1,ρ2,...,ρm, we show that the worst-case combinatorial complexity of the convex hull CHd(Σ) of Σ is Θ(Σ{1≤i≠j≤m}ninj⌊ d/2 ⌋), where ni is the number of ...
Maximum Rectilinear Convex Subsets
Let $P$łabelpage1 be a set of $n$ points in the plane. We consider a variation of the classical Erdös--Szekeres problem, presenting efficient algorithms with $O(n^3)$ running time and $O(n^2)$ space complexity that compute (1) a subset $S$ of $P$ such that ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2016
654 pages
ISBN:9781450340427
DOI:10.1145/2843043
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 February 2016
Check for updates
Qualifiers
- Research-article
Conference
ACSW '16
Acceptance Rates
ACSW '16 Paper Acceptance Rate 77 of 172 submissions, 45%;
Overall Acceptance Rate 204 of 424 submissions, 48%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 118Total Downloads
- Downloads (Last 12 months)8
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in