Observations on optimal parallelizations of two-list algorithm

Author(s)

Alonso Sanches, Carlos Alberto ^[1] ; Soma, Nei Yoshihiro ^[1] ; Yanasse, Horacio Hideki ^[2]

Affiliation

^[1] CTA ITA IEC, Inst Tecnol Aeronaut, BR-12228900 Sao Jose Dos Campos, SP - Brazil

^[2] INPE LAC, Inst Nacl Pesquisas Espaciais, BR-12227010 Sao Jose Dos Campos, SP - Brazil

• Document type: Journal article
• Source: PARALLEL COMPUTING; v. 36, n. 1, p. 65-67, JAN 2010.
• Web of Science Citations: 2

Abstract

For more than three decades, the very well known and famous two-list Horowitz and Sahni algorithm {[}3] remains the serial upper-bound for the 0-1 Knapsack problem with n items (KP01) in a time bounded by O(2(n/2)). Recently, Chedid {[}2] Suggested an optimal parallelization for that algorithm to a KP01 variation - the subset-sum problem - in a PRAM CREW with p = 2(n/8) processors. It is presented here that, in addition to be incomplete, the Chedid result is a particular case given by Sanches et al. {[}6]. (c) 2009 Elsevier B.V. All rights reserved. (AU)

• FAPESP's process: 06/05325-1 - Solving intractable problems through natural computing
• Grantee: Carlos Alberto Alonso Sanches
• Support Opportunities: Scholarships in Brazil - Post-Doctoral