Vol. 22 No.2 | pp.9-14.

A Generalized Subtractive Algorithm for Subset Sum Problem

Abstract This paper presents a subset sum problem (SSP) algorithm which takes the time complexity of O(nlogn). The SSP can be classified into either super-increasing sequence or random sequence depending on the element of Set S. Additive algorithm that runs in O(nlogn) has already been proposed to and utilized for the super-increasing sequence SSP, but exhaustive Brute-Force method with time complexity of O(n2n) remains as the only viable algorithm for the random sequence SSP, which is thus considered NP-complete. The proposed subtractive algorithm basically selects a subset  comprised of values lower than target value t, then sets the subset sum less the target value ...
1|2|3
Copyright © The Institute of Internet, Broadcasting and Communication. All rights reserved.
Address : 610 Dongbu Sunville, #99-6 GaRak-dong, SongPa-gu, Seoul, Korea | Tel : +82-2-407-7718, +82-70-7404-7718, Fax : + 82-2-407-7716 E-mail: iibc@iibc.kr