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.greedy_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)$ and the covering sums; decidable equality on $E$ is required as an instance argument though no notion in the statement refers to it. Six 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}$; a real number $\rho$; then, after the hypotheses on $\rho$ and the certificate, a function $x : S \to \mathbb{R}$.

Hypotheses. Three:

1. $0 < \rho$ — strictly positive, so $\rho = 0$ and negative $\rho$ are excluded.
2. $(\mathcal{C}, y)$ is a $\rho$-greedy certificate for $(A, c)$, unfolding to a conjunction of four parts:
   • $\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$;
   • $\displaystyle \sum_{s \in \mathcal{C}} c_s = \sum_{e \in E} y_e$ — an exact equality between the cost of $\mathcal{C}$ and the total of $y$ over all of $E$, not an inequality;
   • $\displaystyle \forall s \in S,\ \sum_{e \in A_s} y_e \le \rho \cdot c_s$ — a $\rho$-relaxed packing constraint at every index of $S$, with $\rho$ scaling the cost side only.
3. $x$ is a fractional cover of $A$: $\forall s \in S,\ 0 \le x_s$, and $\forall e \in E,\ 1 \le \sum_{s \in N(e)} x_s$. No upper bound on any $x_s$.

Conclusion.

$$\sum_{s \in \mathcal{C}} c_s \;\;\le\;\; \rho \cdot \sum_{s \in S} c_s\, x_s .$$

The same $\rho$ that appears in the relaxed packing constraint is the multiplier in the conclusion. The dual vector $y$ 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. The statement therefore cannot be instantiated at data violating either: the bundle cannot be constructed without proofs of $\forall s,\ 0 \le c_s$ and $\forall e \exists s,\ e \in A_s$.

2. Logical redundancy.

• Nonnegativity of cost is derivable from hypothesis 1 together with the fourth conjunct of hypothesis 2: for each $s$, $0 \le \sum_{e \in A_s} y_e \le \rho\, c_s$ (the left inequality because $y \ge 0$), and dividing by $\rho > 0$ gives $0 \le c_s$. This derivation uses the strict positivity of $\rho$.
• Coverability is derivable from the covering conjunct of hypothesis 2 (a witness in $\mathcal{C}$ is a witness in $S$) and independently from hypothesis 3 (an element with $N(e) = \emptyset$ would make the covering sum $0$, contradicting $1 \le 0$).
• Strict positivity of $\rho$ is not derivable from the other hypotheses: they are satisfiable with $\rho = 0$ — take $c \equiv 0$, $y \equiv 0$, and any covering $\mathcal{C}$, so that $\sum_{s \in \mathcal{C}} c_s = 0 = \sum_e y_e$ and $\sum_{e \in A_s} y_e = 0 \le 0 \cdot c_s$. Hence removing hypothesis 1 would strictly enlarge the set of situations the statement ranges over (all configurations with $\rho \le 0$, which the relaxed packing constraint together with $y \ge 0$ and $c \ge 0$ confines to $\rho\,c_s \ge 0$ for all $s$).
• Dropping the two bundled fields would leave the covered situations unchanged, since hypotheses 1–3 force both properties. No other hypothesis is redundant: the exact equality $\mathrm{coverCost}(c,\mathcal{C}) = \mathrm{pack}(y)$, the covering conjunct, $y \ge 0$, the relaxed packing constraints, and both halves of hypothesis 3 are mutually independent.

3. Arbitrary or specific. The fractional cover is arbitrary: $x$ is universally quantified subject only to feasibility, and the least fractional cost is never mentioned. The cover $\mathcal{C}$ is arbitrary subject to the four certificate conjuncts — nothing identifies it as the output of a greedy procedure or of any procedure, and it is not claimed minimum-cost or minimal. The dual vector $y$ is arbitrary subject to nonnegativity, the exact cost equality, and the $\rho$-relaxed constraints; in particular $y$ is not required to be a dual packing (the unrelaxed inequality $\sum_{e \in A_s} y_e \le c_s$ is not imposed unless $\rho \le 1$ makes it follow). $\rho$ is an arbitrary positive real, tied to nothing else — not to $\Delta$, not to a harmonic number, not to $|E|$ or $|S|$.

4. Cast from $\mathbb{N}$ to $\mathbb{R}$. There is none in this statement: the multiplier is the real parameter $\rho$, and no cardinality, frequency, or maximum frequency appears. The multiplier consequently cannot be $0$: hypothesis 1 asserts $0 < \rho$. For contrast, were $\rho$ permitted to be $0$, the fourth conjunct would read $\sum_{e \in A_s} y_e \le 0$ at every $s$, which with $y \ge 0$ forces $y_e = 0$ at every covered $e$ — i.e. at every $e$, by the covering conjunct — hence $\mathrm{pack}(y) = 0$ and, by the equality conjunct, $\mathrm{coverCost}(c,\mathcal{C}) = 0$, while the right-hand side would be $0 \cdot \mathrm{fracCost}(c,x) = 0$.

5. Degenerate cases.

• $E$ empty. The covering conjunct and $y \ge 0$ are vacuous; every $A_s$ is empty, so the relaxed constraints read $0 \le \rho\,c_s$, which holds since $\rho > 0$ and $c \ge 0$. $\mathrm{pack}(y) = 0$, so the equality conjunct forces $\sum_{s \in \mathcal{C}} c_s = 0$. The covering inequalities of hypothesis 3 are vacuous, leaving only $x \ge 0$, so $\mathrm{fracCost}(c,x) \ge 0$ and the conclusion reads $0 \le \rho \cdot \mathrm{fracCost}(c,x)$ with a nonnegative right side. Note the left side is forced to $0$ even if $\mathcal{C}$ contains positive-cost indices — no such $\mathcal{C}$ satisfies the hypotheses.
• $S$ empty. Then $\mathcal{C} = \emptyset$ and $N(e) = \emptyset$ for all $e$, so hypothesis 3 is satisfiable only when $E$ is empty (and the bundled coverability field forces this anyway); all sums are empty and the conclusion is $0 \le \rho \cdot 0$.
• $\mathcal{C}$ empty. The covering conjunct is then unsatisfiable unless $E$ is empty; in that case $\mathrm{coverCost}(c,\emptyset) = 0 = \mathrm{pack}(y)$ consistently, and the conclusion reads $0 \le \rho \cdot \mathrm{fracCost}(c,x)$.
• $c \equiv 0$. The relaxed constraints give $\sum_{e \in A_s} y_e \le \rho \cdot 0 = 0$, and with $y \ge 0$ this forces $y_e = 0$ for every covered $e$, hence (by the covering conjunct) for all $e$; so $\mathrm{pack}(y) = 0$ and, by the equality conjunct, $\mathrm{coverCost}(c,\mathcal{C}) = 0$. Also $\mathrm{fracCost}(c,x) = 0$, so the conclusion reads $0 \le \rho \cdot 0 = 0$ for every feasible $x$ and every $\rho > 0$.
• Individual zero-cost sets inside the certificate. For any $s$ (in $\mathcal{C}$ or not) with $c_s = 0$, the fourth conjunct gives $\sum_{e \in A_s} y_e \le 0$, and with $y \ge 0$ this forces $y_e = 0$ for every $e \in A_s$. Such an index contributes $0$ to the left side and $0$ to the right side whatever $x_s$ is. Unlike the primal–dual certificate, no equality $\sum_{e \in A_s} y_e = c_s$ is imposed on indices of $\mathcal{C}$; only the global equality $\mathrm{coverCost}(c,\mathcal{C}) = \mathrm{pack}(y)$ is.
• $\rho$ small. For $0 < \rho < 1$ the relaxed constraints are stronger than the unrelaxed packing constraints, and the asserted inequality is correspondingly strong: the cost of $\mathcal{C}$ is bounded by a fraction of the fractional cost of every feasible $x$. As $\rho \to 0^+$ the hypotheses become increasingly restrictive, in the limiting direction forcing $y$ to vanish on all covered elements and hence $\mathrm{coverCost}(c,\mathcal{C}) = 0$.
• $\rho$ large. Both the fourth conjunct and the conclusion weaken; no upper bound on $\rho$ is imposed, and $\rho$ is not required to be an integer or to relate to any structural quantity of the instance.
• Unbounded entries of the fractional cover. Entries $x_s$ may be arbitrarily large (only $x \ge 0$ and the covering inequalities are imposed), making the right-hand side arbitrarily large; entries may be $0$, and all of $S$ is summed over in $\mathrm{fracCost}$. Since $c \ge 0$ and $x \ge 0$, the right-hand side is always nonnegative.
• Empty sets $A_s$ are permitted; distinct indices may carry equal subsets; $\mathcal{C}$ may contain indices whose removal would still leave a cover.

Not asserted. No claim that $\mathcal{C}$ arises from a greedy algorithm, or from any algorithm — "greedy" names the predicate only, whose content is exactly the four conjuncts listed. No claim that $\mathcal{C}$ is a minimum-cost cover, that $x$ is of least fractional cost, or that $y$ is a maximum packing; the least-cover-cost and least-fractional-cost notions are unused, so nothing is asserted about any optimum, nor about a harmonic-number or logarithmic approximation factor. No claim that $y$ is a dual packing in the unrelaxed sense. No claim that a $\rho$-greedy certificate exists for any given instance or for any particular $\rho$, and no claim that the hypotheses are jointly satisfiable. No claim that $\rho$ is the least valid multiplier, no tightness or attainment, no reverse inequality, no strict inequality, and no comparison with the maximum frequency.