| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | mtc-m16.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 6qtX3pFwXQZ3r59YDa/H6rRe |
| Repository | sid.inpe.br/iris@1916/2005/08.08.16.52 (restricted access) |
| Last Update | 2005:08.08.03.00.00 (UTC) administrator |
| Metadata Repository | sid.inpe.br/iris@1916/2005/08.08.16.52.26 |
| Metadata Last Update | 2018:06.05.01.28.30 (UTC) administrator |
| Secondary Key | INPE-12937-PRE/8216 |
| ISSN | 1014-8264 |
| Citation Key | YanasseCont:1991:CoPrCP |
| Title | A Complexidade do Problema CPM com Função de Custo Não-Convexa  |
| Project | Otimização combinatória, algorítmos e heurísticas |
| Year | 1991 |
| Month | Dec. |
| Access Date | 2024, Apr. 28 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 209 KiB |
| 2. Context | |
| Author | 1 Yanasse, Horacio Hideki 2 Contador, José Luiz |
| Resume Identifier | 1 8JMKD3MGP5W/3C9JHCP |
| Group | 1 LAC-INPE-BR |
| Affiliation | 1 Instituto Nacional de Pesquisas Espaciais, Laboratório Associado de Computação e Matemática Aplicada, (INPE. LAC) 2 Universidade Estadual Paulista, Faculdade de Engenharia de Guaratinguetá (UNESP.FEG) |
| Journal | Investigación Operativa |
| Volume | 2 |
| Number | 2 |
| Pages | 121-125 |
| History (UTC) | 2006-01-24 11:11:53 :: sergio -> administrator :: 2007-04-03 15:37:45 :: administrator -> sergio :: 2008-01-07 12:49:51 :: sergio -> marciana :: 2008-02-19 12:27:12 :: marciana -> administrator :: 2018-06-05 01:28:30 :: administrator -> marciana :: 1991 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Keywords | COMPUTER SCIENCE Computational complexity PERT/CPM Project management CPM (cost-time-tradeoff problem) COMPUTAÇÃO APLICADA Complexidade computacional Gestão de projetos |
| Abstract | Neste trabalho prova-se que o problema CPM (cost-time tradeoff problem) com funções de custo não-convexas é NP-Hard. A prova é feita através da conversão de um problema reconhecidamente pertencente à classe NP-Hard em uma instância particular do problema CPM. Vários autores têm apresentado algoritmos não polinomiais para tratar que, de fato, é pouco provável a existência de algoritmos polinomiais para resolver este tipo de problema. ABSTRACT: In this paper it is shown that the cost-time tradeoff problem with non-convex functions is NP-Hard. The proof is made by the conversion of a known HP-hard problem in a particular instance of the cost-time tradeoff problem. Many autors have proposed non-polynomial algorithms to treat this problem without focusing its complexity. The proof here presented shows that, in fact, the existence of polynomial algorithms to deal with this problem is very unlikely. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > A Complexidade do... |
| 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 | complexidade problema.pdf |
| User Group | administrator marciana sergio |
| Visibility | shown |
| Copy Holder | SID/SCD |
| Archiving Policy | denypublisher denyfinaldraft |
| Read Permission | deny from all and allow from 150.163 |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | PORTALCAPES |
| Host Collection | sid.inpe.br/banon/2003/08.15.17.40 |
| 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 readergroup rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url versiontype |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |