Inclusion-wise extremal knapsack problems are (mostly) hard to approximate
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.18017
curl -X POST /api/v1/records/arxiv/2610.18017/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.18017/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'