Pairs of knapsack value and size patterns that can actually happen
Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
Discrete MathematicsData Structures and Algorithms
Summary
This paper studies a problem related to the knapsack, a way to pick items with values that fit into limited spaces. When you measure best values you can get for two different size limits, you get two patterns. The authors investigate which pairs of such patterns are possible. They find a mathematical system that checks some necessary conditions, but also show this is not always enough. They classify some cases fully and analyze the complexity of deciding if a pair is possible.
What this means in practice
- •For optimization software developers: Determine which value and size trade-off patterns can arise when designing knapsack-based optimization tools with two capacity constraints.
- •For algorithm designers: Use the complexity and characterization results to guide the development of efficient algorithms for inverse knapsack problems with two capacity settings.
A theory result. No direct application yet.
Authors
Prashant Chaudhary, Kapil Khandelwal
Abstract
One item set evaluated at two capacities $R<D$ produces two concave hulls of optimal value against cardinality. We ask which prescribed pairs arise. Exchange arguments give a necessary system on vertex witnesses, exchange closure (EC), whose scalar consequences form the linear closure. We exhibit a pair satisfying every scalar test that fails EC, so the linear closure is strictly larger already at larger terminal count three; and a globally coherent EC witness admitting no common-size representation although its target pair is realizable. Under a cardinality cap, a four-band classification of one family gives exact thresholds for cap-four realizability, uncapped realizability and the vertex-only capped closure. Pairs whose larger terminal count is at most two are characterized. Under the explicit encoding the decision problem lies in $Σ_2^p$ and is polynomial-time for fixed terminal cardinalities. Exact finite certificates establish agreement of the scalar and witness conditions on six specified domains; sufficiency of uncapped EC remains open.