No polynomial kernels for knapsack

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_#.

Subjects

Knapsack

Polynomial kernels

Compositions

Number of different weights

Number of different profits

DDC Class

004: Computer Sciences

510: Mathematics

Funding(s)

Multivariate Algorithmen für Scheduling mit hoher Multiplizität

More Funding Information

Supported by the ISF, grant No. 1070/20.

Publication version

publishedVersion

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

LIPIcs.ICALP.2024.83.pdf

Size

818.4 KB

Format

Adobe PDF

Options

No polynomial kernels for knapsack