Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
En palabras de los autores
One item set evaluated at two capacities 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 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.
Apareció: jueves, 24 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 28 pages. Code, certificates and verification: https://doi.org/10.5281/zenodo.22823629