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.primalDual_certificate_bound

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)$, the frequencies, and the covering sums; decidable equality on $E$ is required as an instance argument though no notion in the statement refers to it. Five explicit arguments, in order: a set-cover instance $I$ (carrying $A$, $c$, the proof $\forall s,\ 0 \le c_s$, and the proof $\forall e \exists s,\ e \in A_s$); a finite index set $\mathcal{C} \subseteq S$; a function $y : E \to \mathbb{R}$; then, after the certificate hypothesis, a function $x : S \to \mathbb{R}$.

Hypotheses. Two, independent of each other:

1. $(\mathcal{C}, y)$ is a primal–dual certificate for $(A, c)$, unfolding to the conjunction of
   • $\forall e \in E,\ \exists s \in \mathcal{C},\ e \in A_s$ ($\mathcal{C}$ covers $E$);
   • $\forall e \in E,\ 0 \le y_e$ and $\forall s \in S,\ \sum_{e \in A_s} y_e \le c_s$ ($y$ is a dual packing, the inequalities holding at every index of $S$);
   • $\forall s \in \mathcal{C},\ \sum_{e \in A_s} y_e = c_s$ (exact tightness on $\mathcal{C}$).
2. $x$ is a fractional cover of $A$, unfolding to $\forall s \in S,\ 0 \le x_s$ together with $\forall e \in E,\ 1 \le \sum_{s \in N(e)} x_s$. No upper bound is placed on any $x_s$.

Conclusion.

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

with $\Delta$ cast into $\mathbb{R}$. The dual vector $y$ occurs only in the hypothesis; it does not appear in the conclusion.

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

2. Logical redundancy.

• Nonnegativity of cost is derivable from the dual-packing part of hypothesis 1: $0 \le \sum_{e \in A_s} y_e \le c_s$ for every $s$, the left inequality holding because $y \ge 0$.
• Coverability is derivable twice over: from the covering conjunct of hypothesis 1 (a witness in $\mathcal{C}$ is a witness in $S$), and independently from hypothesis 2 (if $N(e)$ were empty the covering sum would be $0$, contradicting $1 \le 0$).
• Inside the certificate, the packing inequality at indices $s \in \mathcal{C}$ is implied by the tightness equality there, so those inequalities are only independent at indices outside $\mathcal{C}$.
• Nothing else is redundant: hypothesis 1 does not follow from hypothesis 2 or conversely, and $y \ge 0$, the covering conjunct, the tightness conjunct, and both halves of hypothesis 2 are otherwise independent.

Dropping the two bundled fields would leave the covered situations unchanged, since the remaining hypotheses force both properties.

3. Arbitrary or specific. The fractional cover is arbitrary: $x$ is universally quantified subject only to feasibility, so the inequality is asserted for every feasible $x$ separately; the least fractional cost is never mentioned, and no $x$ is claimed optimal. The cover $\mathcal{C}$ is arbitrary subject to being part of a certificate — not claimed minimum-cost or minimal. The dual vector $y$ is arbitrary subject to being a dual packing tight on $\mathcal{C}$ — not claimed to be of maximum value.

4. Cast from $\mathbb{N}$ to $\mathbb{R}$. The cast occurs at the multiplier $\Delta$, computed in $\mathbb{N}$ as a supremum of cardinalities over $E$ (empty supremum $= 0$) and cast to multiply the real $\mathrm{fracCost}(c,x)$. When the cast value is $0$ the claim reduces to

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

$\Delta = 0$ means all frequencies vanish or $E$ is empty; since coverability (bundled, and also implied by either hypothesis) gives $f(e) \ge 1$ for each $e \in E$, under these hypotheses $\Delta = 0$ exactly when $E$ is empty. The hypotheses then force each side: every $A_s$ is empty, so tightness gives $c_s = 0$ for all $s \in \mathcal{C}$ and the left side is $0$; the right side is $0 \cdot \mathrm{fracCost}(c,x) = 0$ regardless of $x$ (which is then constrained only by $x \ge 0$, its covering inequalities being vacuous). The claim becomes $0 \le 0$.

5. Degenerate cases.

• $E$ empty. Covering and $y \ge 0$ vacuous; $\Delta = 0$; tightness forces $c_s = 0$ on $\mathcal{C}$; both sides $0$. $x$ is unconstrained beyond nonnegativity, and $y$ entirely unconstrained.
• $S$ empty. Then $\mathcal{C} = \emptyset$ and $N(e) = \emptyset$ for all $e$, so hypothesis 2 is satisfiable only when $E$ is empty (and the bundled coverability field already forces this); all sums are empty and the conclusion is $0 \le 0$.
• $\mathcal{C}$ empty. The covering conjunct is then unsatisfiable unless $E$ is empty; in that case both sides are $0$.
• $c \equiv 0$. The packing inequalities plus $y \ge 0$ force $y_e = 0$ for every covered $e$, hence for all $e$; $\mathrm{fracCost}(c,x) = 0$ and $\mathrm{coverCost}(c,\mathcal{C}) = 0$, so the conclusion reads $0 \le \Delta \cdot 0 = 0$ for every feasible $x$, however large its entries.
• Individual zero-cost sets inside the certificate. For $s \in \mathcal{C}$ with $c_s = 0$, tightness forces $\sum_{e \in A_s} y_e = 0$ and hence $y_e = 0$ for all $e \in A_s$; for $s \notin \mathcal{C}$ with $c_s = 0$ the packing inequality forces the same. Such indices contribute $0$ to the left side and $0$ to the right side whatever $x_s$ is.
• $\Delta$ small or large. $\Delta = 1$ leaves $\mathrm{coverCost}(c,\mathcal{C}) \le \mathrm{fracCost}(c,x)$; larger $\Delta$ weakens the claim. $\Delta$ is a property of the whole family $A$ over all of $S$; nothing ties it to $\mathcal{C}$, to $x$, or to the type cardinalities.
• Unbounded entries of the fractional cover. Entries $x_s$ may be arbitrarily large, making the right-hand side arbitrarily large; entries may also be $0$, and every index of $S$ is summed over in $\mathrm{fracCost}$. Since $c \ge 0$ and $x \ge 0$, the right-hand side is always nonnegative.
• $\rho$. Not applicable: the multiplier is the cast maximum frequency, not a free parameter.

Not asserted. No claim that $\mathcal{C}$ is a minimum-cost cover, that $x$ is a minimum-cost fractional cover, or that $y$ is a maximum packing; the least-cover-cost and least-fractional-cost notions are not used, so nothing is said about the integral or fractional optimum as such. No claim that $\mathrm{pack}(y)$ equals or bounds either side. No claim that a certificate or a fractional cover exists, and no claim that the hypotheses are jointly satisfiable. No tightness, attainment, reverse inequality, or strict inequality; no claim that $\Delta$ is the smallest valid multiplier. Nothing about the indicator vector of $\mathcal{C}$ being a fractional cover, nothing about algorithms or online arrival.

---