Algorithms for the problem of K maximum sums and a VLSI algorithm for the K maximum subarrays problem

Author

Bae, Sung Eun ; Takaoka, Tadao

Author_Institution

Dept. of Comput. Sci., Canterbury Univ., Christchurch, New Zealand

fYear

2004

fDate

10-12 May 2004

Firstpage

247

Lastpage

253

Abstract

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³) time. Finally, we present a VLSI K maximum subarrays algorithm with O(K * n) steps and a circuit size of O(n²), which is cost-optimal in parallelisation of the sequential algorithm.

Keywords

VLSI; computational complexity; parallel algorithms; sequences; K maximum subarrays problem; K maximum subsequences problem; K maximum sums; VLSI algorithm; circuit size; cost-optimal algorithm; overlapping property; sequential algorithm; Algorithm design and analysis; Circuits; Computer science; Data analysis; Data mining; Image processing; Parallel algorithms; Pattern recognition; Phase change random access memory; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on

ISSN

1087-4089

Print_ISBN

0-7695-2135-5

Type

conf

DOI

10.1109/ISPAN.2004.1300488

Filename

1300488