Options
No polynomial kernels for knapsack
Citation Link: https://doi.org/10.15480/882.13125
Publikationstyp
Conference Paper
Publikationsdatum
2024-07
Sprache
English
First published in
Number in series
Article Number
83
Citation
International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-specific parameter. Such algorithms provide a theoretical model for data reduction and preprocessing and are central in the area of parameterized complexity. In this way, a kernel for Knapsack for some parameter k reduces any instance of Knapsack to an equivalent instance of size at most f(k) in polynomial time, for some computable function f. When f(k) = k^{O(1)} then we call such a reduction a polynomial kernel. Our study focuses on two natural parameters for Knapsack: The number w_# of different item weights, and the number p_# of different item profits. Our main technical contribution is a proof showing that Knapsack does not admit a polynomial kernel for any of these two parameters under standard complexity-theoretic assumptions. Our proof discovers an elaborate application of the standard kernelization lower bound framework, and develops along the way novel ideas that should be useful for other problems as well. We complement our lower bounds by showing that Knapsack admits a polynomial kernel for the combined parameter w_# ⋅ p_#.
Schlagworte
Knapsack
Polynomial kernels
Compositions
Number of different weights
Number of different profits
DDC Class
004: Computer Sciences
510: Mathematics
More Funding Information
Supported by the ISF, grant No. 1070/20.
Publication version
publishedVersion
Loading...
Name
LIPIcs.ICALP.2024.83.pdf
Size
818.4 KB
Format
Adobe PDF