{"id":"arxiv/2610.18017","url":"https://arxiv.org/abs/2610.18017","tags":["cs.DS","math.OC"],"score":0,"title":"Inclusion-wise extremal knapsack problems are (mostly) hard to approximate","domain":"cs.DS","source":"arxiv","authors":["Fabio Ciccarelli","Fabio Furini","Ulrich Pferschy","Elena Rener"],"reviews":0,"subject":"cs.DS","summary":"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 $\\mathrm{NP}$-hard and pseudo-polynomially solvable, as is the classical KP, but their approximability is fundamentally different: unless…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}