Parallel time and space upper-bounds for the subset-sum problem

Autor(es)

Sanches, C. A. A. ^[1] ; Soma, N. Y. ^[1] ; Yanasse, H. H. ^[2]

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

^[1] ITA, BR-12228900 Sao Jose Dos Campos, SP - Brazil

^[2] INPE, Sao Jose Dos Campos - Brazil

• Tipo de documento: Artigo Científico
• Fonte: THEORETICAL COMPUTER SCIENCE; v. 407, n. 1-3, p. 342-348, NOV 6 2008.
• Citações Web of Science: 8

Resumo

Three new parallel scalable algorithms for solving the Subset-Sum Problem in O(n/p(c - w(min))) time and O(n + c) space in the PRAM model are presented, where n is the number of objects, c is the capacity, w(min) is the smallest weight and p is the number of processors. These time and space bounds are better than the direct parallelization of Bellman's algorithm, which was the most efficient known result. (C) 2008 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 99/09483-5 - Algoritmos para problemas de corte e empacotamento em ambientes distribuidos e paralelos.
• Beneficiário: Carlos Alberto Alonso Sanches
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• 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