| Texto completo | |
| Autor(es): |
Pedrosa, Lehilton L. C.
;
da Silva, Mauro R. C.
;
Schouery, Rafael C. S.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 3-pg., 2023-01-01. |
| Resumo | |
We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 20/13162-2 - Problemas de empacotamento com número fixo de recipientes |
| Beneficiário: | Mauro Roberto Costa da Silva |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Processo FAPESP: | 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas |
| Beneficiário: | Rafael Crivellari Saliba Schouery |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |