%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@resumeid
%@resumeid
%@resumeid 8JMKD3MGP5W/3C9JHCP
%@archivingpolicy denypublisher denyfinaldraft36
%@usergroup administrator
%@usergroup simone
%3 An optimal and scalable.pdf
%X In this paper, we suggest a parallel algorithm based on a shared memory SIMD architecture for solving an n item subset-sum problem in time O(2n/2/p) by using p = 2q processors, . This approach is an optimal and scalable parallelization of the well known two-list Horowitz and Sahnis algorithm, which is still the best complexity time bound for solving the Knapsack problem in a serial environment.
%8 Jan.
%N 2
%T An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
%@secondarytype PRE PI
%K Subset-sum problem, Knapsack problem, Parallel algorithms, PRAM machines.
%@visibility shown
%@group
%@group
%@group LAC-INPE-MCT-BR
%@secondarykey INPE-15022-PRE/9933
%@copyholder SID/SCD
%@issn 0377-2217
%2 sid.inpe.br/mtc-m17@80/2007/12.03.13.27.08
%@affiliation Instituto Tecnológico de Aeronáutica (ITA)
%@affiliation Instituto Tecnológico de Aeronáutica (ITA)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%B European Journal of Operational Research
%P 870-879
%4 sid.inpe.br/mtc-m17@80/2007/12.03.13.27
%D 2007
%V 176
%A Sanches, C. A. A.,
%A Soma, N. Y.,
%A Yanasse, Horacio Hideki,
%@dissemination WEBSCI; PORTALCAPES.
%@area COMP