| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | mtc-m16b.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 6qtX3pFwXQZGivnK2Y/SkSJU |
| Repository | sid.inpe.br/mtc-m17@80/2007/12.03.13.27 (restricted access) |
| Last Update | 2007:12.03.13.27.06 (UTC) administrator |
| Metadata Repository | sid.inpe.br/mtc-m17@80/2007/12.03.13.27.08 |
| Metadata Last Update | 2018:06.05.03.35.51 (UTC) administrator |
| Secondary Key | INPE-15022-PRE/9933 |
| ISSN | 0377-2217 |
| Citation Key | SanchesSomaYana:2007:OpScPa |
| Title | An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem  |
| Year | 2007 |
| Month | Jan. |
| Access Date | 2024, Apr. 28 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 187 KiB |
| 2. Context | |
| Author | 1 Sanches, C. A. A. 2 Soma, N. Y. 3 Yanasse, Horacio Hideki |
| Resume Identifier | 1 2 3 8JMKD3MGP5W/3C9JHCP |
| Group | 1 2 3 LAC-INPE-MCT-BR |
| Affiliation | 1 Instituto Tecnológico de Aeronáutica (ITA) 2 Instituto Tecnológico de Aeronáutica (ITA) 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
| Journal | European Journal of Operational Research |
| Volume | 176 |
| Number | 2 |
| Pages | 870-879 |
| History (UTC) | 2007-12-19 23:09:11 :: simone -> administrator :: 2008-06-29 02:38:11 :: administrator -> simone :: 2011-05-18 21:37:56 :: simone -> administrator :: 2012-10-24 00:06:34 :: administrator -> simone :: 2007 2013-02-20 15:20:09 :: simone -> administrator :: 2007 2018-06-05 03:35:51 :: administrator -> marciana :: 2007 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Keywords | Subset-sum problem Knapsack problem Parallel algorithms PRAM machines |
| Abstract | 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. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > An optimal and... |
| 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 | An optimal and scalable.pdf |
| User Group | administrator simone |
| Visibility | shown |
| Copy Holder | SID/SCD |
| Archiving Policy | denypublisher denyfinaldraft36 |
| Read Permission | deny from all and allow from 150.163 |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | WEBSCI; PORTALCAPES. |
| Host Collection | lcp.inpe.br/ignes/2004/02.12.18.39 cptec.inpe.br/walmeida/2003/04.25.17.12 |
| 6. Notes | |
| Empty Fields | alternatejournal archivist callnumber copyright creatorhistory descriptionlevel documentstage doi e-mailaddress electronicmailaddress format isbn label lineage mark mirrorrepository nextedition notes orcid parameterlist parentrepositories previousedition previouslowerunit progress project readergroup rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url versiontype |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |