Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
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 Σ2p 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.
Related
- Generalized Spectral Closedness and the Nonexistence of Walk-Realizable Supporters for Split Graphs
- Realizable Cohomology Classes of Dihedral and Generalized Quaternion Groups
- Hybridizing 0/1 Knapsack and Priority-Aware TSP for Vehicle Routing: an Applied Variant of the TSP with Profits
- Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
- A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
BibTeX
@misc{chaudhary2026inverse,
title = {{Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?}},
author = {Prashant Chaudhary and Kapil Khandelwal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28128},
eprint = {2609.28128},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28128},
}
RIS
TY - UNPB
TI - Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
AU - Prashant Chaudhary
AU - Kapil Khandelwal
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28128
UR - https://arxiv.org/abs/2609.28128
AB - 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.
ER -