- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the minimum number of fixed counterexamples needed to cover all compatible measurement batches of a given size for a fixed pair of models. Under diagonal ellipsoidal uncertainty, this becomes a set cover problem in which both queries and covering sets satisfy the same knapsack constraint. The authors develop grouped linear programming bounds, quantify aggregation loss under a demand-stability condition, and characterize the coarsest partition satisfying this condition. They also construct examples separating library size from aggregate coverage statistics and demonstrating gaps between joint LP bounds and counting or packing bounds. Experiments examine the applicability and tightness of the bounds, their impact on integer capacity decisions, and computational performance.
Critical strengths
The paper studies a meaningful structural question: how much information about covering cost can be retained after grouping coordinates? Distinguishing demand feasibility from covering-set feasibility identifies two different sources of aggregation loss.
The framework provides computable fractional-cover certificates. Theorem 2 quantifies the loss when only demand feasibility is preserved, with an order-tight worst-case dependence on the retention factor. Theorem 3 makes the demand-stability requirement constructive by computing its coarsest valid partition.
Critical weaknesses
The theoretical increment over established covering and symmetry methods is modest. Theorem 2 combines a model-specific safe-contraction condition with standard subset sampling and fractional-weight rescaling. The structural part of Theorem 3 follows from classical twin equivalence and threshold ordering. These results organize known techniques effectively, but provide limited new understanding of what makes the shared-knapsack covering problem substantially different.
More importantly, the grouping criterion does not control the covering information that the method aims to preserve. Theorem 3 minimizes the number of groups needed to preserve demand feasibility; Theorem 2 evaluates the loss after a partition has been chosen. This leaves the problem of finding a compact, accurate representation unresolved. Indeed, with the same two-group budget, an alternative partition can recover the fractional optimum exactly while the prescribed median refinement produces an upper-to-lower bound ratio of (\Omega(E^2)). Thus, the method can lose substantial information even when an exact representation is available at the same size.
The separation results do not resolve this central limitation. They show that coarse statistics and packing can miss covering complexity, but do not establish that joint LP constraints are essential once counting is allowed to select more informative demand classes. Consequently, the evidence for a substantial advance in preserving or recovering covering information remains limited.
Questions for authors
What connects the proposed grouping rule to the goal of preserving covering information? Consider (k=2), with (2m-2) coordinates of weight (1), two of weight (m-1), and (T=2m-3/2). All pairs are feasible, so the coarsest demand-stable partition has one group. With a two-group budget, median refinement yields (U\ge\binom{m}{2}) and (D\le6), whereas separating the light and heavy coordinates gives (D=U=\tau^*). The example persists under sufficiently small distinct perturbations. How does the framework address this unbounded loss relative to an exact representation at the same group budget? What theoretical guarantee supports the choice of groups beyond preserving demand feasibility?
Within the shared-knapsack model, does joint LP analysis retain a nonvanishing asymptotic advantage over the strongest uniform-counting bound on an arbitrary demand subfamily, [ \max_{\varnothing\ne S\subseteq\mathcal U_k} \frac{|S|} {\max_{C:,w(C)\le T}|{B\in S\subseteq C}|},? ] This directly tests whether joint pricing captures covering information that optimized counting cannot recover. Separations from aggregate statistics, packing, or unions of a prescribed set of demand types do not settle this question. What structural conclusion about the additional power of joint pricing can the paper establish at this level?