PaperlayerView exact revision on arXiv

Source-linked AI summary

Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?

Prashant Chaudhary, Kapil Khandelwal

arXiv:2609.28128v1math.OCcs.DMcs.DS

TL;DR

The paper asks which pairs of value-cardinality hulls can arise from one item set evaluated at two capacities. It develops exchange and witness conditions, then shows scalar tests suffice in some regimes but fail at larger terminal count three. It also distinguishes target realizability from completion of a specified witness.

  • Problem

    The paper asks which prescribed pairs of optimal-value-versus-cardinality hulls can be produced by one shared item set at two capacities.

    Source: §1 · p. 1

  • Method

    Exchange arguments derive vertex-witness closure and scalar bounds, while pruning and rescaling give an equivalent full-witness formulation of realizability.

    Source: §1 · p. 1, §2 · p. 3

  • Results

    Scalar bounds characterize realizability for bw≤2 but fail at bw=3, and a globally coherent EC witness can lack a size completion although its target pair is realizable.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results distinguish realizing a target pair from completing a chosen witness and identify terminal-count regimes where scalar tests suffice.

    Source: §1 · pp. 1–2

    The finite-search bound is not a practical algorithm, and infeasibility on a chosen grid does not prove unrestricted non-realizability.

    Source: §6 · p. 21

Abstract

from arXiv · show

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 $\Sigma_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.

1 Introduction

The paper asks which pairs of value-cardinality hulls can arise from one shared item set, distinguishing target realizability from completion of a specified witness. It develops exchange-based tests and identifies regimes where scalar conditions do and do not characterize realizability.

1 Introduction

  • Exchange arguments yield EC and scalar necessary bounds, while pruning and rescaling equate realizability with full-witness closure using at most N* items.N* is the sum of the abscissae of all positive vertices of the two hulls.Source: §1 · p. 2
  • A globally coherent EC witness may fail to admit item sizes even when its target pair is realizable.This separates completion of a specified witness from existence of a witness for the target.Source: §1 · pp. 1–2
  • Under cardinality caps, an irrelevance bound and a four-band classification distinguish cap dependence from failure of vertex-only capped EC.The classification concerns cap-four realizability, uncapped realizability, and the vertex-only capped closure.Source: §1 · p. 2
  • For larger terminal count bw≤2, scalar bounds characterize realizability.On six specified integer-slope domains, dominance and two scalar inequalities also decide every target.Source: §1 · p. 2
  • At larger terminal count bw=3, dominance and scalar bounds accept a pair rejected by EC, so linear closure strictly exceeds exchange closure.The counterexample shows scalar tests do not characterize realizability in this regime.Source: §1 · p. 2
  • Six constructive regions provide explicit instances and expose a rational gap in the first five.The construction predicates and their regions are not presented as a classification of all rational pairs with bw=3.Source: §1 · p. 2, §1.1 · p. 3
  • The decision problem is polynomial-time for fixed terminal counts, while its hardness remains open.Exact finite certificates establish scalar-witness agreement on six specified integer-slope domains.Source: §1 · p. 2

1.1 Relation to prior work

  • Adjacent inverse and parametric knapsack work studies different inputs or quantifiers, not reconstruction of shared-instance cardinality-hull pairs.The paper distinguishes this inverse existence question from optimizing a given instance or prescribing a single value profile.Source: §1 · p. 1, §1.1 · pp. 2–3

2 Setting and hull reduction

The paper studies which two increasing concave value-cardinality hulls can arise from the same item set at capacities R and D. Hull vertices, rather than every raw count value, determine the target, and realizability has an equivalent full-witness formulation.

Setting and hull reduction

  • Rational item sizes can be scaled to integers together with capacities, while item values remain rational.Items individually infeasible at D may be discarded; considered items have size at most D.Source: §2 · p. 3
  • The target is the upper concave hull through counts up to the first maximizing count, not the full raw optimum profile.Intermediate points on a linear run need not be attained by any set.Source: §2 · p. 3
  • A pair is realizable when one finite instance reproduces both specified hulls, with an equivalent full-witness formulation using at most N* items.The hulls need not specify every raw count value.Source: §2 · pp. 3–4
  • For nonnegative per-item cost c, the upper hull determines the best net value; off-hull points do not affect that envelope.Points after the first global maximum cannot improve it for c ≥ 0; at c = 0, only the envelope value is asserted.Source: §2 · pp. 3–4
  • At D = 5 and R = 3, items (4, 3), (3, 1), (3, 1), and (2, 1) realize two prescribed hulls with the same items.The size-three item fits alone at R, while the three unit-size items fit together there.Source: §2 · p. 4

3 The three closures and necessity

The section separates scalar tests, exchange-closed vertex witnesses, and full witnesses, deriving necessary exchanges and scalar bounds for realizability. The full-witness condition is exact, while scalar closure is strictly larger than exchange closure at larger terminal count three.

3 The three closures and necessity

  • EC retains labeled vertex sets, declared remainder-feasible subsets, and value-preserving overlap matchings, but requires neither sizes nor globally consistent identities.The two exchanges constrain long-item removal and pair exclusion; satisfying local exchanges need not make a specified witness completable.Source: §3 · p. 5
  • Every realizable pair satisfies exchange closure (EC), obtained by choosing attaining sets at positive vertices and applying two feasibility exchanges.Subset feasibility, item identity, and the exchange lemma supply the witness conditions.Source: §3 · p. 5

3.1 Useful scalar corollaries

  • The all-long bounds apply at a larger-hull vertex n when h_n > ρ_1; their antecedent differs from that of the pair-complement bound.The bounds extend between remainder vertices by concavity and interpolation.Source: §3.1 · p. 6
  • For a larger-hull vertex n ≥ 3, the pair-complement bound constrains the larger hull using the best nonoverlapped item, whether the overlap is empty or a singleton.The exchange argument limits the attaining-set overlap to at most one item.Source: §3.1 · p. 6
  • For rational a > 0 and a/2 < r < a, (0, a, 2a, 3a) and (0, a, a + r, a + 2r) satisfy dominance but are unrealizable at any integer cap.The terminal-count-four pair-complement bound is violated.Source: §3.1 · p. 7

3.2 Full witnesses and the closure hierarchy

  • A realizable pair has a pruned realization with at most N* items, retaining one attaining set at every positive vertex.Deleting other items cannot increase profile values and preserves the selected vertex values.Source: §3.2 · p. 7
  • Full-witness closure (FWC) is exactly realizability: one common positive-size threshold representation must support the vertex attainments and all subset bounds.Pairwise overlap matchings alone need not provide globally coherent item identities.Source: §3.2 · pp. 7–8
  • Linear closure strictly contains EC already at larger terminal count three, while sufficiency of uncapped EC remains open.A separate obstruction distinguishes completion of a specified globally coherent witness from existence of a full witness for its target.Source: §3.2 · p. 8

4 Where the chain collapses

The scalar and witness conditions coincide for larger terminal count at most two, while terminal-count-three results establish a coverage map but not a complete rational classification. A scalar counterexample shows that the linear closure is strictly larger than exchange closure at terminal count three.

4 Where the chain collapses

  • For larger terminal count at most two, dominance and the all-long bounds characterize realizability, so L = EC = FWC.When bw = 2 and h2 > ρ1, the additional restriction is (1) at n = 2 and the terminal remainder count.Source: §4 · p. 9
  • Dominance suffices under either free mixing, where remainder slopes are a submultiset of larger slopes, or the stated exclusive-long-item slope conditions.The constructions use unit-size short items; in the exclusive-long case, long items cannot fit together and each admits at most n −1 short items.Source: §4 · p. 9

4.1 A coverage map for terminal count three

  • For larger terminal count three, A, B, T1, and T2 cover many targets, but the coverage table retains residuals across multiple vertex types.In the displayed boxes, residuals have br = 3 but are distributed among vertex types {1, 3}, {2, 3}, and {1, 2, 3}; T6 also has a br = 2 family.Source: §4.1 · p. 10, Table 2 · p. 10

4.2 Two size patterns beyond the base cover

  • T5 realizes its stated two-hull profile using an isolated best short item, but its equal-first-value condition excludes some residual cases.The construction's remainder count-two point may be raised to its hull value; T5 does not cover every residual even when first hull values are equal.Source: §4.2 · p. 11
  • For every rational v with 3/2 < v ≤ 5/3, T6 realizes a family outside the hypotheses of A, B, T1, T2, and T5.This establishes a gap in that construction cover, not a counterexample to EC sufficiency.Source: §4.2 · p. 12

4.3 The scalar tests are not sufficient

  • At bw = 3, a target can satisfy dominance and every applicable scalar test yet remain unrealizable, so L is strictly larger than EC.The example has h3 = ρ1, making the all-long antecedent silent at the terminal vertex, while the pair-complement bound holds with equality.Source: §4.3 · pp. 12, 14
  • The nonrealizability proof rules out both possible overlap sizes between the attaining triples, using incompatible strict size inequalities in the one-item-overlap case.The argument starts with exactly one long and one short item among the relevant values, then derives opposite inequalities for d(y2) and d(z2) + d(z3).Source: §4.3 · p. 13
  • The scalar counterexample also fails EC, confirming L ≠ EC at bw = 3 without resolving whether every globally coherent EC witness completes.The obstruction in this example is obtained from a local witness.Source: §4.3 · pp. 13–14

5 Witness and cap separations

This section examines how witness completion, realizability, and cardinality caps relate to closure tests. It gives exact cap thresholds for a linear-remainder family and exactness results for subset-enriched capped closure on specified domains, while documenting cases where vertex-only closure accepts unrealizable pairs and broader closure remains a relaxation.

5.1 Completion of a specified witness

  • A globally coherent EC witness can lack any size completion even though another instance realizes the same target pair.The obstruction is a balanced trade: the same item incidences would have to fit sets totaling at most the labeled capacities and fail to fit sets totaling strictly more. This witness also satisfies the subset-enriched closure at K = 4, while its target remains realizable at that cap.Source: §5.1 · pp. 14–15

5.2 The capped closure hierarchy

  • Capped and uncapped realizability coincide for K ≥ max{1, N*}.At the equality case, the remainder cap can still exclude the full ground set, but that set cannot change the target hull.Source: §5.2 · p. 17
  • For the family Hw = (0, a, a + b, a + 2b), Hr = (0, c, 2c, 3c), four thresholds divide cap-four closure from capped and uncapped realizability.Writing H = a + 2b, when 3c < H < 9c/2 the pair fails vertex-only capped EC at K = 4 and is unrealizable at every integer cap and uncapped; when 9c/2 ≤ H < 6c it satisfies that closure but is still unrealizable. When 6c ≤ H < 9c it is realizable precisely at K = 4, while H ≥ 9c gives uncapped realizability and realizability at every K ≥ 4. Thus enlarging the cap can destroy realizability.Source: §5.2 · pp. 17, 19

5.3 Separation from vertex-only capped EC

  • Exchanging a permitted subset of an r-vertex yields an additional necessary bound under a cap, also required by the subset-enriched capped closure.The bound adds a restriction beyond the uncapped test only under a cap; uncapped, it follows from that test and concavity of Hr.Source: §5.3 · p. 19
  • For 9c/2 ≤ a + 2b < 6c, the pair satisfies vertex-only capped EC at K = 4 but is unrealizable at K = 4, any other integer cap, or uncapped.This concerns the vertex-only capped truncation, which drops exchanges whose output count exceeds K.Source: §5.3 · p. 19
  • A vertex-only cap-four witness accepts the false positive pair (0, 5, 9, 13), (0, 3, 5, 7), which the lemma excludes because 13 < 40/3.Its archived witness has all-long X1 and X3, empty overlaps, and declared families containing only the empty set.Source: §5.3 · p. 19
  • On the slope-five dominated domain, subset-enriched capped closure coincides with realizability for K = 3 through 6, but remains a relaxation beyond the classified family.The exactness claim is supported by positive certificates; it does not establish general sufficiency outside the particular family.Source: §5.3 · p. 20
  • For Theorem 5.7’s family at K = 4, subset-enriched closure matches realizability exactly iff H ≥ 6c.Necessity follows from an admissible count-four exchange removing the cheapest X3 item and inserting the two most valuable Z3 items; sufficiency follows from the seven-item realization and Lemma 5.4.Source: §5.3 · p. 20

6 Decidability and complexity

The section establishes complexity bounds under the explicit encoding and gives a polynomial-time algorithm for fixed terminal cardinalities. It also explains why the upper bound retains a universal subset check and why finite search bounds do not automatically yield practical algorithms.

Fixed-witness completion

  • Completing a fixed EC witness reduces to a rational linear program with |E| + 2 variables and potentially exponentially many rows.A positive common margin encodes strict nonfits; rational sizes can then be scaled to integers.Source: §6 · p. 20

Small realizations

  • Every realizable pair has a small rational realization with at most N* items and polynomial encoding length.The proof bounds rational vertices for sizes and values; N* is polynomial in the explicit input length.Source: §6 · pp. 20–21

Complexity bounds

  • Theorem 6.3 places realizability in Σ_2^p and gives polynomial-time decidability for fixed terminal cardinalities.Both results also hold with a specified cardinality cap.Source: §6 · p. 21

Membership proof

  • A polynomial-size guessed instance and attaining sets form the existential witness, but a universally quantified subset check remains necessary.The subset and capacity bit are checked by a polynomial-time predicate against the hull bounds.Source: §6 · p. 21

Limits of numerical search

  • A finite determinant bound does not make a chosen small grid complete, so grid infeasibility cannot establish unrestricted non-realizability.Floating-point feasibility also requires exact reconstructed-instance checks before it counts as a positive certificate.Source: §6 · p. 21

Open complexity questions

  • Whether the variable-terminal-count problem is NP, NP-hard, or Σ_2^p-hard remains open.The polynomial-bit bound does not remove the universal subset check or supply a rigidity construction.Source: §6 · p. 21

7 Which inclusions are strict?

The paper separates scalar closure from exchange closure and exchange closure from full realizability. The first gap is demonstrated, while sufficiency of uncapped EC and broader capped characterizations remain open.

Uncapped closure gaps

  • The scalar-to-EC gap is settled, but whether EC equals full witness closure for arbitrary uncapped targets remains open.The paper also asks whether equality holds when the larger terminal count is three.Source: §7 · p. 22

Specified-witness completion

  • The balanced-trade family does not separate EC from realizability: another witness realizes every displayed target.Thus completing every coherent EC witness is too strong a strategy for the existential questions.Source: §7 · p. 22

Capped closure

  • The four-band capped classification settles every cap on the linear-remainder family, but does not provide sizes for a general specified witness.The capped version of Theorem 5.2 rules out that stronger completion conclusion.Source: §7 · p. 22

Scalar tests

  • Theorem 4.6 identifies a scalar-test failure at a terminal vertex with slope ρ1 and count four rather than five.Table 2 also shows residual template coverage cannot be confined to one vertex type.Source: §7 · p. 22

Future scalar tests

  • A replacement scalar test must cover a terminal vertex whose slope equals ρ1, and the paper asks whether a broader test characterizes realizability.The open question concerns cases where some member of a w-attaining set is long, without requiring hn > ρ1.Source: §7 · p. 22

Reproducibility

The deposited archive supports the paper’s finite checks, while general results rely on mathematical proofs. Repeated executions reproduced the publication-facing outputs, but the checks are not independent human proof verification.

Reproducibility

  • Three complete executions on Linux x86_64 and macOS arm64 regenerated all 30 publication-facing files and produced the same 7,044 decisions.The runs agreed on 5,516 positive certificates and 1,528 exact exclusions.Source: Reproducibility · p. 22

Evidence scope

  • The archive supports finite assertions, whereas parameter-wide theorems depend on proofs; computational checks do not replace proof reading or mathematical peer review.The authors also state that exact programs verify finite claims on declared domains, not general results.Source: Reproducibility · p. 22

Data and code

  • The deposited archive contains the data and code for finite checks, with a versioned artifact and tagged repository identified separately.The artifact DOI and repository are distinct records.Source: Reproducibility · p. 23

A Two three-count templates

The three-count constructions use long-item values and sizes to attain prescribed hull vertices while keeping other feasible sets within hull bounds. The section gives a three-long-item template, a condition simplifying its use, and a two-long-item template.

A Two three-count templates

  • T1 separates three large values from short items, while T2 lets the best short join the triple when the terminal slope is smaller.When br = 0, the construction sets ρ1 = 0.Source: A Two three-count templates · p. 23
  • The T1 construction chooses three long-item values to attain the terminal value, then uses sizes to control which partner items can join them.It verifies that mixed sets stay within the hull bounds and that required larger-count vertices are attained.Source: A Two three-count templates · p. 23
  • When h3 > ρ1 and either 2 is not a vertex or 2Hr(br) ≤ h1 + h3, dominance and the all-long bounds characterize realizability.The proof shows the T1 parameter interval is nonempty under these conditions.Source: A Two three-count templates · p. 23
  • For the two-long-item construction, a best short helps attain the triple, while an optional partner allows pair attainment without exceeding the hull bounds.The construction assigns sizes so the two longs admit only one short, and adds a partner only when needed for pair attainment.Source: A Two three-count templates · pp. 23–24

B.1 Domains and the collapse of the uncapped hierarchy

On six specified integer-slope domains, exact finite certificates establish agreement among the scalar and witness conditions. This agreement is limited to those domains and does not imply sufficiency for all rational targets.

B.1 Domains and the collapse of the uncapped hierarchy

  • The filtered domains omit br = 0 and apply additional stated vertex and remainder filters; the dominated domains include every pair in their slope boxes.These filters define candidate domains and are not applied to the dominated capped comparisons.Source: §B.1 · p. 24
  • On each of six specified domains, the finite certificates establish FWC = EC = L.Positive instances are checked by exact subset enumeration, while every exclusion violates a proved bound.Source: §B.1 · pp. 24–25
  • Within the stated integer-slope domains, realizability is equivalent to dominance and inequalities (1) and (3), with their antecedents respected.No separate check of (2) or exchange-witness optimization is needed for this finite decision.Source: §B.1 · p. 25
  • The finite equivalence does not extend to all rational targets: a scalar-admissible unrealizable pair has largest slope seven, outside all six domains.The paper states that sufficiency of uncapped EC is not asserted by these propositions.Source: §B.1 · p. 25

B.2 Coverage and the last residuals

The constructions cover most realizable targets in two dominated boxes with br ≤ 3; the remaining targets are concentrated at br = 3, but not in one vertex type.

B.2 Coverage and the last residuals

  • Of 933 and 2086 realizable targets in the two boxes, A, B, T1, and T2 cover 925 and 2059, respectively.The residuals number 8 and 27, and all have br = 3, but they are not concentrated in one w-vertex type.Source: §B.2 · p. 25
  • T5 covers 5 of the 8 residuals in one box and 13 of the 27 in the other.Every other residual already has an exact instance, but those instances do not constitute additional parameter-wide construction theorems.Source: §B.2 · p. 25
  • The listed eight-item instance attains count two with two six-valued items and count three with three five-valued items.Its size assignments constrain feasible mixtures of those items and the three unit shorts so their values remain within the target hull.Source: §B.2 · p. 25

B.3 The capped hierarchy and independent item censuses

Finite comparisons characterize several capped classes and compare cap-four with uncapped realizability on a fixed target set. The section also checks a linear-remainder family and two exhaustive item censuses.

B.3 The capped hierarchy and independent item censuses

  • Among the same 1089 slope-five targets, exactly 26 pairs are realizable at K = 4 but not uncapped, and none are realizable uncapped but not at K = 4.The set includes 35 zero-remainder targets; one of the 26 pairs belongs to the family in Theorem 5.7.Source: §B.3 · p. 26
  • At K = 4, ten vertex-only false positives are rejected by the truncated bound (7); the finite table does not establish general capped sufficiency.The enriched and FWC columns are certified exactly on these comparisons.Source: §B.3 · p. 26
  • The linear-remainder family checks recorded uncapped dispositions against H ≥ 9c, with no mismatches in the stated integer domains or additional rational examples.Sampled-cap predictions are regression evidence; the assertion for every K ≥ 4 in case (iv) is proved by Theorem 5.7.Source: §B.3 · p. 26
  • Two exhaustive item-level censuses record 844 and 613 distinct hull pairs, and their exact EC checks reject none of the realized pairs.The censuses enumerate all item multisets within their stated value, size, item-count, and capacity bounds.Source: §B.3 · p. 26

B.4 Verification and implementation

The verification pipeline runs two catalog checks and regenerates results using exact positive and negative checks. Reproducibility rests on exact verification of the deposited catalog and deterministic regeneration, not identical optimizer rediscovery.

B.4 Verification and implementation

  • Two catalog checks cover combinations and chords, then bitmasks and monotone-chain hulls, before result files are regenerated.The two exact positive checkers use different algorithms and both use rational arithmetic.Source: §B.4 · p. 26
  • The certificate checker also verifies negative inequalities, the four-row completion dual, domain keys, and ten capped witnesses.The tabulation script computes Table 2 from certified targets and construction predicates without searching domains.Source: §B.4 · p. 27
  • Exploratory candidates used integer sizes with D = 60 and a HiGHS-backed solver, but accepted positives are reconstructed and verified exactly.The deposited certificate path uses only the Python standard library and no numerical solver.Source: §B.4 · p. 27
  • Reproducibility means exact catalog verification and deterministic regeneration, not byte-identical optimizer rediscovery, since targets can have multiple realizations.Independent solver runs therefore need not select the same witness.Source: §B.4 · p. 27
  • Thirty instances were recertified exactly on the D = 60 integer grid, preserving source-certificate values and each labeled subset’s two-threshold fit pattern.These finite certificates do not substitute for parameter-wide proofs.Source: §B.4 · p. 27
Loading 2609.28128v1…