Complexidade do Positional Knapsack Problem

  • Lehilton L. C. Pedrosa UNICAMP
  • Mauro R. C. Silva UNICAMP
  • Rafael C. S. Schouery UNICAMP

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.
Publicado
31/07/2022
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.