loading...
Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem
Hong Kong, SAR, China May 10-May 12
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.13004882004 International Symposium on Paral ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Sung Eun Bae, Tadao Takaoka, "Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 247, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2004.1300488,
author = {Sung Eun Bae and Tadao Takaoka},
title = {Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2004},
issn = {1087-4089},
pages = {247},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.1300488},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem
SN - 1087-4089
SP
EP
A1 - Sung Eun Bae,
A1 - Tadao Takaoka,
PY - 2004
KW - maximum subarray
KW - maximum subsequence
KW - prefix sums
KW - VLSI
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
Sung Eun Bae, University of Canterbury, Christchurch, New Zealand
Tadao Takaoka, University of Canterbury, Christchurch, New Zealand
Given an array of positive and negative values, we consider the problem of K maximum sums. When an overlapping property needs to be observed, previous algorithms for the maximum sum are not directly applicable. We designed an O(K * n) algorithm for the K maximum subsequences problem. This was then modified to solve the K maximum subarrays problem in O(K * n{3}) time. Finally, we present a VLSI K maximum subarrays algorithm with O(K * n) steps and a circuit size of O(n{2}), which is cost-optimal in parallelisation of the sequential algorithm.
Index Terms:
maximum subarray, maximum subsequence, prefix sums, VLSI
Citation:
Sung Eun Bae, Tadao Takaoka, "Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem," ispan, pp.247, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.