Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Sanches, C. A. A. [1] ; Soma, N. Y. [1] ; Yanasse, H. H. [2]
Total Authors: 3
Affiliation:
[1] ITA, BR-12228900 Sao Jose Dos Campos, SP - Brazil
[2] INPE, Sao Jose Dos Campos - Brazil
Total Affiliations: 2
Document type: Journal article
Source: THEORETICAL COMPUTER SCIENCE; v. 407, n. 1-3, p. 342-348, NOV 6 2008.
Web of Science Citations: 8
Abstract

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)

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