| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | marte3.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 6qtX3pFwXQZ3r59YCT/H3KP9 |
| Repository | sid.inpe.br/iris@1905/2005/08.04.02.49 (restricted access) |
| Last Update | 2013:04.25.12.42.50 (UTC) administrator |
| Metadata Repository | sid.inpe.br/iris@1905/2005/08.04.02.49.27 |
| Metadata Last Update | 2018:06.06.03.55.42 (UTC) administrator |
| Secondary Key | INPE-9837-PRE/5421 |
| ISSN | 0167-8191 |
| Label | 10509 |
| Citation Key | SanchesSomaYana:2002:CoPaAl |
| Title | Comments on parallel algorithms for the knapsack problem  |
| Project | FAPESP (grant 99/09483-5). |
| Year | 2002 |
| Secondary Date | 20021009 |
| Month | Oct. |
| Access Date | 2024, May 05 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 66 KiB |
| 2. Context | |
| Author | 1 Sanches, Carlos Alberto Alonso 2 Soma, Nei Yoshihiro 3 Yanasse, Horacio Hideki |
| Group | 1 2 3 LAC-INPE-MCT-BR |
| Affiliation | 1 Instituto Tecnológico de Aeronáutica - CTA/ITA/IEC 2 Instituto Tecnológico de Aeronáutica - CTA/ITA/IEC 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
| Author e-Mail Address | 1 2 nysoma@comp.ita.br |
| Journal | Parallel Computing |
| Volume | 28 |
| Number | 101-2 |
| Pages | 1501-1505 |
| History (UTC) | 2013-04-20 17:28:15 :: administrator -> jefferson :: 2002 2013-04-25 12:42:52 :: jefferson -> administrator :: 2002 2018-06-06 03:55:42 :: administrator -> marciana :: 2002 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Version Type | publisher |
| Keywords | knapsack problem parallel algorithm shared memory multiprocessor SIMD machine |
| Abstract | Chang et al. [Parallel Comput. (1994)233)introduced a parallel algorithm based on a shared memory SIMD architecture for the generation phase of the classic Horowitz and Sahni [J. ACM 21(2)(1974)277]two-list serial algorithm for the knapsack problem. They claimed that their parallel generation phase could be accomplished in time O((n/8)^(2)) and in space O(2^(n/4)) with O(2^(n/8)) processors. We prove that their results are not correct, i.e., that the suggested scheme time and space complexity should be bounded, instead, by O(n2^(n/2)) and O(2^(n/2)), respectively. These results also invalidate the performance analysis of the more recent Lou and Chang [Parallel Comput. (1997)1985]algorithm. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > Comments on parallel... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| Language | en |
| Target File | 1-s2.0-S0167819102001503-main.pdf |
| User Group | administrator jefferson |
| Visibility | shown |
| Archiving Policy | denypublisher denyfinaldraft24 |
| Read Permission | deny from all and allow from 150.163 |
| Update Permission | not transferred |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | WEBSCI; PORTALCAPES. |
| Host Collection | sid.inpe.br/banon/2001/04.03.15.36 |
| 6. Notes | |
| Empty Fields | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel doi e-mailaddress format isbn lineage mark mirrorrepository nextedition notes orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup resumeid rightsholder schedulinginformation secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |