Complexidade do Positional Knapsack Problem
Resumo
Neste resumo, apresentamos o Positional Knapsack Problem (PKP) e demonstramos que ele é NP-difícil. O PKP é uma variante do Knapsack Problem (KP) em que o valor de um item varia linearmente de acordo com a posição em que ele é adicionado. Essa mudança na valoração adiciona diversas propriedades não intuitivas ao problema que não valem para o KP e, de fato, o PKP não é uma generalização do KP. Para demonstrar a NP- dificuldade, reduzimos uma variante do Partition Problem a uma instância de PKP cuidadosamente construída, de forma a recuperar algumas propriedades normalmente esperadas para variantes do KP.
Palavras-chave:
Problema da Mochila, Algoritmos de aproximação, NP-dificuldade
Referências
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability, volume 174. freeman San Francisco.
Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Introduction to np-completeness of knapsack problems. In Knapsack Problems, pages 483–493. Springer.
Kovalyov, M. Y. and Pesch, E. (2010). A generic approach to proving np-hardness of partition type problems. Discrete applied mathematics, 158(17):1908–1912.
Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Introduction to np-completeness of knapsack problems. In Knapsack Problems, pages 483–493. Springer.
Kovalyov, M. Y. and Pesch, E. (2010). A generic approach to proving np-hardness of partition type problems. Discrete applied mathematics, 158(17):1908–1912.
Publicado
31/07/2022
Como Citar
PEDROSA, Lehilton L. C.; SILVA, Mauro R. C.; SCHOUERY, Rafael C. S..
Complexidade do Positional Knapsack Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 53-56.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.222786.
