Read-backs: certificate bounds

Throughout, the shared vocabulary is expanded as follows. A set-cover instance $I$ on two types $E$ (elements) and $S$ (set indices) is a bundle of exactly four components:

• a family $A : S \to \mathcal{P}_{\mathrm{fin}}(E)$, i.e. a finite subset $A_s \subseteq E$ for each index $s$;
• a cost function $c : S \to \mathbb{R}$;
• a proof of nonnegative cost: $\forall s \in S,\ 0 \le c_s$;
• a proof of coverability: $\forall e \in E,\ \exists s \in S,\ e \in A_s$.

Derived notions, all expanded inline in each section below:

$$N(e) \;=\; \{\, s \in S \;:\; e \in A_s \,\}, \qquad f(e) \;=\; |N(e)| \in \mathbb{N}, \qquad \Delta \;=\; \sup_{e \in E} f(e) \in \mathbb{N},$$

where $N(e)$ is formed by filtering the whole index type $S$, $f(e)$ is a cardinality in $\mathbb{N}$, and $\Delta$ is a supremum in $\mathbb{N}$ taken over all of $E$ — a supremum of an empty family, which is $0$ when $E$ is empty. Further:

$$\mathrm{coverCost}(c, \mathcal{C}) = \sum_{s \in \mathcal{C}} c_s, \qquad \mathrm{fracCost}(c, x) = \sum_{s \in S} c_s x_s, \qquad \mathrm{pack}(y) = \sum_{e \in E} y_e .$$

$\mathrm{coverCost}$ sums only over the given finite index set $\mathcal{C}$; $\mathrm{fracCost}$ sums over all of $S$; $\mathrm{pack}$ sums over all of $E$.

---

PrimalDualOnline.SetCover.coverCost_le_maxFrequency_mul_packing

Binders and instance arguments. Universally quantified over arbitrary types $E$ and $S$ (implicit), with four typeclass arguments: $E$ finite, $S$ finite, equality on $E$ decidable, equality on $S$ decidable. Either type may be empty. Decidable equality on $S$ is needed to form $N(e)$ and hence the frequencies; decidable equality on $E$ is required as an instance argument though no notion in the statement refers to it. Three explicit arguments: a set-cover instance $I$ on $E, S$ (carrying $A$, $c$, the proof $\forall s,\ 0 \le c_s$, and the proof $\forall e \exists s,\ e \in A_s$); a finite set of indices $\mathcal{C} \subseteq S$; and a function $y : E \to \mathbb{R}$.

Hypothesis. A single hypothesis: $(\mathcal{C}, y)$ is a primal–dual certificate for $(A, c)$. This unfolds to a conjunction of three parts, the middle one itself a conjunction:

1. $\mathcal{C}$ covers $E$: $\forall e \in E,\ \exists s \in \mathcal{C},\ e \in A_s$.
2. $y$ is a dual packing: $\forall e \in E,\ 0 \le y_e$, and $\forall s \in S,\ \sum_{e \in A_s} y_e \le c_s$ — the inequality holding at every index of $S$, not only those in $\mathcal{C}$.
3. Tightness on $\mathcal{C}$: $\forall s \in \mathcal{C},\ \sum_{e \in A_s} y_e = c_s$, an exact equality.

Conclusion.

$$\sum_{s \in \mathcal{C}} c_s \;\;\le\;\; \Delta \cdot \sum_{e \in E} y_e, \qquad \Delta = \sup_{e \in E} \bigl| \{ s \in S : e \in A_s \} \bigr| ,$$

with $\Delta$ a natural number cast into $\mathbb{R}$. The frequencies counted in $\Delta$ range over all of $S$, including indices outside $\mathcal{C}$.

1. Nonnegativity of cost; every element in some set. Both are fields of the bundled argument $I$, not loose hypotheses. The statement therefore cannot be instantiated at data violating either: $I$ cannot be constructed without both proofs.

2. Logical redundancy.

• Nonnegativity of cost is derivable from conjunct 2: $y \ge 0$ makes $\sum_{e \in A_s} y_e$ a sum of nonnegative terms, so $0 \le \sum_{e \in A_s} y_e \le c_s$ for every $s$.
• Coverability is derivable from conjunct 1: a witness $s \in \mathcal{C}$ with $e \in A_s$ is in particular a witness $s \in S$ with $e \in A_s$.
• Within the certificate there is a partial overlap: for indices $s \in \mathcal{C}$, the packing inequality of conjunct 2 follows from the equality of conjunct 3. So conjunct 2's family of inequalities is doing independent work only at indices outside $\mathcal{C}$; its nonnegativity half, $y \ge 0$, is not derivable from anything else, nor is conjunct 1, nor conjunct 3 (the equality does not follow from the inequality).

Dropping the two bundled fields would not change the situations covered: any $A, c, \mathcal{C}, y$ satisfying the certificate hypothesis already satisfies both. Replacing conjunct 2's inequalities by the restriction "$\forall s \notin \mathcal{C}$" would likewise cover exactly the same situations.

3. Arbitrary or specific. No fractional cover appears in this statement. The cover $\mathcal{C}$ is arbitrary, constrained only by being a covering index set that is tight for $y$; it is not claimed to be minimum-cost, minimal, or produced by any procedure. The dual vector $y$ is arbitrary, constrained only by being a dual packing tight on $\mathcal{C}$; it is not claimed to be of maximum packing value.

4. Cast from $\mathbb{N}$ to $\mathbb{R}$. The cast occurs at the multiplier: $\Delta$, the maximum frequency, is computed in $\mathbb{N}$ (a supremum of cardinalities over the finite type $E$, with the empty supremum equal to $0$) and then cast into $\mathbb{R}$ to be multiplied by the real number $\mathrm{pack}(y)$. When the cast value is $0$, the conclusion reduces to

$$\sum_{s \in \mathcal{C}} c_s \;\le\; 0 .$$

$\Delta = 0$ means every element has frequency $0$, or that there is no element at all. Coverability (a field of $I$, and also a consequence of conjunct 1) gives $f(e) \ge 1$ for every $e \in E$, so under these hypotheses $\Delta = 0$ happens exactly when $E$ is empty. In that case the hypotheses force both sides to be $0$: each $A_s$ is a subset of the empty type and hence empty, so conjunct 3 gives $c_s = \sum_{e \in A_s} y_e = 0$ for every $s \in \mathcal{C}$, whence $\mathrm{coverCost}(c,\mathcal{C}) = 0$; and $\mathrm{pack}(y) = 0$ as an empty sum, so the right-hand side is $0 \cdot 0 = 0$. The claim becomes $0 \le 0$.

5. Degenerate cases.

• $E$ empty. As just described: covering is vacuous, $y \ge 0$ is vacuous, $\Delta = 0$, $\mathrm{pack}(y) = 0$, tightness forces $c_s = 0$ on $\mathcal{C}$, and the conclusion is $0 \le 0$. Every $y : E \to \mathbb{R}$ is admissible (there are no elements to constrain).
• $S$ empty. The only finite index set is $\mathcal{C} = \emptyset$, and the bundled coverability field then requires $E$ empty as well; all three quantities $\mathrm{coverCost}$, $\Delta$, $\mathrm{pack}$ are $0$.
• $\mathcal{C}$ empty. Conjunct 1 then demands, for each $e$, an index in the empty set — impossible unless $E$ is empty. So $\mathcal{C} = \emptyset$ is admissible only in the $E$-empty case, where the conclusion is $0 \le 0$.
• $c \equiv 0$. Conjunct 2 forces $\sum_{e \in A_s} y_e \le 0$, and with $y \ge 0$ this gives $y_e = 0$ for every $e$ belonging to some $A_s$, i.e. (by coverability) for every $e$. Then $\mathrm{pack}(y) = 0$ and $\mathrm{coverCost}(c,\mathcal{C}) = 0$: the conclusion is $0 \le \Delta \cdot 0 = 0$.
• Individual zero-cost sets inside the certificate. If $c_s = 0$ for some $s \in \mathcal{C}$, conjunct 3 gives $\sum_{e \in A_s} y_e = 0$, and with $y \ge 0$ this forces $y_e = 0$ for every $e \in A_s$. The same conclusion follows from conjunct 2 for a zero-cost index outside $\mathcal{C}$. Thus zero-cost sets pin the dual to zero on all their elements.
• $\Delta$ small or large. $\Delta = 1$ (every element in exactly one set) leaves the conclusion $\mathrm{coverCost}(c,\mathcal{C}) \le \mathrm{pack}(y)$; large $\Delta$ weakens it. Nothing in the statement bounds $\Delta$ against $|\mathcal{C}|$, $|S|$, or $|E|$, nor relates $\Delta$ to $\mathcal{C}$ in any way — it is a property of the whole family $A$.
• $\rho$. Not applicable: no external multiplier appears; the multiplier is the cast maximum frequency.
• Unbounded entries of a fractional cover. Not applicable: no fractional cover appears.
• Indices in $\mathcal{C}$ may carry empty or duplicated subsets; $\mathcal{C}$ may contain indices whose removal would still leave a cover.

Not asserted. No claim that $\mathcal{C}$ is a minimum-cost cover or that $y$ has maximum packing value; the least-cover-cost and least-fractional-cost notions in the vocabulary are not mentioned, so nothing is asserted about any optimum. No comparison with the fractional relaxation. No claim that a primal–dual certificate exists for any instance, nor that the hypotheses are satisfiable. No claim that $\Delta \ge 1$, that the bound is tight or attained, no reverse inequality, and no strict inequality. Nothing about algorithms, online arrival, or how $\mathcal{C}$ and $y$ might be produced.

---