TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-02

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Weighted greedy set cover has approximation factor H_n

Statement

On a feasible weighted set-cover instance with $n = ∣ U ∣$ , the greedy algorithm returns a cover in polynomial time with total cost at most $H_{n} O P T$ . For $n = 0$ both costs are zero. Thus it is an $H_{n}$ -approximation for $n \geq 1$ .

Facts & Assumptions

Given: A feasible weighted set-cover instance with universe $U$ of $n$ elements and a minimum total cost $O P T$ , together with a full run of the weighted greedy algorithm.

[F1]

The greedy algorithm repeatedly chooses a listed set of positive newly covered count minimizing cost divided by that count, ties going to the smallest input index, charges each newly covered element that same ratio, and returns no set when $U$ is empty; the listed family covers $U$ , so every round before termination finds a positive newly covered count. (Weighted greedy set cover and element charges)

[F2]

If $r \geq 1$ elements remain uncovered before a greedy step, the price chosen per newly covered element is at most $O P T / r$ ; ordering elements by first coverage with in-round ties by the fixed order of $U$ , the $j$ -th element receives charge at most $O P T / (n - j + 1)$ . (The greedy charge on each newly covered element is at most OPT divided by the remaining count)

[F3]

The harmonic numbers are $H_{n} = \sum_{j = 1}^{n} 1 / j$ for $n \geq 1$ and $H_{0} = 0$ . (Harmonic numbers for set-cover analysis)

[F4]

Every instance of the stated domain has a feasible solution, optimum values are attained nonnegative rationals, and a polynomial-time $ρ$ -approximation for a minimization problem returns on every instance a feasible solution of value at most $ρ$ times the optimum. (Optimization problems and approximation ratios)

Proof

technique · direct

1.1F1givenconstruct

Each round of the greedy algorithm covers at least one element that was uncovered before it, because the chosen set has positive newly covered count; hence after at most $n$ rounds the set of uncovered elements is empty, the algorithm halts, and the chosen list is a feasible cover of $U$ . The total cost of the chosen cover equals the sum of the charges of all elements, since each chosen set's cost is divided equally among exactly the elements that it newly covers, and every element is newly covered in exactly one round.

1.2F1F3F4givenalgebra

If $n = 0$ , that is $U = \emptyset$ , the algorithm returns the empty cover of cost $0$ , which is feasible; every feasible cover has nonnegative cost, so $O P T = 0$ , and the asserted bound reads $0 \leq H_{0} \cdot 0 = 0$ by [F3].

2.1F2step 1.1algebra

Assume $n \geq 1$ and order the elements by first coverage, breaking ties within a round by the fixed order of $U$ . For the $j$ -th element of this order the charging bound [F2] gives ${charge}_{j} \leq O P T / (n - j + 1)$ , a valid inequality because the round of first coverage has a positive remaining count and the index satisfies $n - j + 1 \geq 1$ .

3.1F3step 1.1step 2.1algebra

Summing the bounds of step 2.1 over $j = 1, \dots, n$ and substituting $k = n - j + 1$ , the total cost of the greedy cover satisfies $\sum_{j = 1}^{n} {charge}_{j} \leq \sum_{j = 1}^{n} O P T / (n - j + 1) = O P T \sum_{k = 1}^{n} 1 / k = H_{n} O P T$ by [F3]. The total cost is the sum of the charges by step 1.1, so the greedy cover has cost at most $H_{n} O P T$ .

4.1F1F4step 1.2step 3.1algebra∎

For $n \geq 1$ the algorithm returns a feasible cover of cost at most $H_{n} O P T$ in deterministic polynomial time: there are at most $n$ rounds by step 1.1, each round scans the finitely many listed sets, computes exact rational ratios with positive denominators, and performs exact comparisons; for $n = 0$ the bound is the zero identity of step 1.2. By [F4] the procedure is a polynomial-time $H_{n}$ -approximation for weighted set cover.

Depends on

Used by

A four-element greedy set-cover charge calculation Example

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Williamson and Shmoys, The Design of Approximation Algorithms, §1.6 Theorem 1.11 with proof, printed pp. 25–26 (standard reference, not scraped)
Ghaffari, Advanced Algorithms, Lecture 1: Approximation Algorithms I, §2.1 Theorem 3, PDF pp. 2–3 (standard reference, not scraped)