Observations on optimal parallelizations of two-list algorithm

Autor(es)

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

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: PARALLEL COMPUTING; v. 36, n. 1, p. 65-67, JAN 2010.
• Citações Web of Science: 2

Resumo

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)

• Processo FAPESP: 06/05325-1 - Resolução de problemas intratáveis através de computação natural
• Beneficiário: Carlos Alberto Alonso Sanches
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado