Complexity of the Positional Knapsack Problem

  • Lehilton L. C. Pedrosa UNICAMP
  • Mauro R. C. Silva UNICAMP
  • Rafael C. S. Schouery UNICAMP
DOI: https://doi.org/10.5753/etc.2022.222786

Abstract


In this work, we present the Positional Knapsack Problem (PKP) and demonstrate that it is NP-hard. PKP is a variant of the Knapsack Problem (KP) in which the value of an item varies linearly according to the position in which it is added. This change in valuation adds several non-intuitive properties to the problem that do not hold for KP because PKP is not a generalization of KP. To demonstrate the NP-hardness, we reduce a variant of the Partition Problem to a carefully constructed instance of PKP in order to retrieve some properties normally expected for variants of KP.

Keywords: Knapsack Problem, Approximation Algorithms, NP-Hardness

References

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.
Published
2022-07-31
How to Cite

Select a Format
PEDROSA, Lehilton L. C.; SILVA, Mauro R. C.; SCHOUERY, Rafael C. S.. Complexity of the Positional Knapsack Problem. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.