Inclusion-wise extremal knapsack problems are (mostly) hard to approximate
Abstract
We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given n items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knapsack Packing Problem seeks a minimum-cost packing for capacity c to which no item can be added, while the Maximum-Profit Minimal Knapsack Cover Problem seeks a maximum-profit cover for threshold d from which no item can be removed. Both problems are weakly NP-hard and pseudo-polynomially solvable, as is the classical KP, but their approximability is fundamentally different: unless P=NP, with positive values neither problem admits a polynomial-time 2p(n)-approximation for any polynomial p; allowing zero values rules out every multiplicative factor. Even with unit costs for packing and unit profits for covering, neither admits an n1−ε-approximation for any fixed ε>0, whereas a trivial n-approximation exists. We identify restrictions that restore approximability. If every item weighs at least a fixed fraction of the capacity, respectively of the threshold, both problems can be solved exactly in polynomial time. For the cover problem, if each weight wi satisfies wi−1≥δ(d−1), we give an approximation scheme for arbitrary profits whose running time is polynomial in n, 1/ε, and 1/δ. If values equal weights, a fully polynomial-time approximation scheme (FPTAS) was already known for the packing problem; we give an FPTAS for the cover problem, improving on the previously known factor $2$. If value-to-weight ratios differ by at most a factor κ, we obtain a (1+ε)κ-approximation for both problems.
Related
- Fixed-Point Formulation and Parallel Averaged Operator Algorithms for Generalized Variational Inclusion Problems
- A Time-Varying Coefficient-Based Fixed-Time Neurodynamic Approach for Generalized Monotone Inclusion Problems and Its Applications
- Turán-type extremal problems for unbalanced signed graphs
- On extremal problems related to the Krzyż conjecture
- Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems
BibTeX
@misc{ciccarelli2026inclusionwise,
title = {{Inclusion-wise extremal knapsack problems are (mostly) hard to approximate}},
author = {Fabio Ciccarelli and Fabio Furini and Ulrich Pferschy and Elena Rener},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18017},
eprint = {2610.18017},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18017},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Inclusion-wise extremal knapsack problems are (mostly) hard to approximate
AU - Fabio Ciccarelli
AU - Fabio Furini
AU - Ulrich Pferschy
AU - Elena Rener
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.18017
UR - https://arxiv.org/abs/2610.18017
AB - We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given n items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knapsack Packing Problem seeks a minimum-cost packing for capacity c to which no item can be added, while the Maximum-Profit Minimal Knapsack Cover Problem seeks a maximum-profit cover for threshold d from which no item can be removed. Both problems are weakly NP-hard and pseudo-polynomially solvable, as is the classical KP, but their approximability is fundamentally different: unless P=NP, with positive values neither problem admits a polynomial-time 2^p(n)-approximation for any polynomial p; allowing zero values rules out every multiplicative factor. Even with unit costs for packing and unit profits for covering, neither admits an n^1−ε-approximation for any fixed ε>0, whereas a trivial n-approximation exists. We identify restrictions that restore approximability. If every item weighs at least a fixed fraction of the capacity, respectively of the threshold, both problems can be solved exactly in polynomial time. For the cover problem, if each weight w_i satisfies w_i−1≥δ(d−1), we give an approximation scheme for arbitrary profits whose running time is polynomial in n, 1/ε, and 1/δ. If values equal weights, a fully polynomial-time approximation scheme (FPTAS) was already known for the packing problem; we give an FPTAS for the cover problem, improving on the previously known factor $2$. If value-to-weight ratios differ by at most a factor κ, we obtain a (1+ε)κ-approximation for both problems.
ER -