ExampleConstruction: AI-generatedVerification: 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.

A four-element greedy set-cover charge calculation

Example

Take $U = {1, 2, 3, 4}$ , $S_{1} = {1, 2}$ of cost $2$ , $S_{2} = {3, 4}$ of cost $2$ , and $S_{3} = U$ of cost $5$ . Greedy chooses $S_{1}$ then $S_{2}$ (input-order tie), charges each element $1$ , and costs $4 = O P T$ . The pointwise bounds $O P T / 4$ , $O P T / 3$ , $O P T / 2$ , $O P T$ are conservative: the actual charges satisfy them with equality only at the first index, and the correct uncovered count must be used at each round.

Facts & Assumptions

Given: The weighted set-cover instance with universe $U = {1, 2, 3, 4}$ , listed sets $S_{1} = {1, 2}$ , $S_{2} = {3, 4}$ , $S_{3} = U$ of costs $2, 2, 5$ , and the weighted greedy algorithm run in the listed order.

[F1]

The greedy algorithm chooses a listed set of positive newly covered count minimizing cost divided by that count, ties going to the smallest input index, and charges every newly covered element that same ratio; the total cost of the chosen cover is the sum of all charges. (Weighted greedy set cover and element charges)

[F2]

With $r \geq 1$ elements uncovered before a step, the chosen price is at most $O P T / r$ , and the $j$ -th element in first-coverage order receives charge at most $O P T / (n - j + 1)$ for a universe of size $n$ . (The greedy charge on each newly covered element is at most OPT divided by the remaining count)

[F3]

For this instance the greedy cover has total cost at most $H_{n} O P T$ with $H_{n} = \sum_{j = 1}^{n} 1 / j$ and $H_{0} = 0$ . (Weighted greedy set cover has approximation factor H_n, Harmonic numbers for set-cover analysis)

Verification

technique · direct

1.1F1givenalgebra

The cover ${S_{1}, S_{2}}$ has cost $2 + 2 = 4$ . Every cover containing $S_{3}$ costs at least $5$ , since costs are nonnegative; every cover not containing $S_{3}$ must contain $S_{1}$ to cover element $1$ and $S_{2}$ to cover element $3$ , hence costs at least $4$ . Therefore the minimum cover cost is $O P T = 4$ .

2.1F1step 1.1algebra

Initially all four elements are uncovered, so $r = 4$ and the ratios are $2 / 2 = 1$ for $S_{1}$ , $2 / 2 = 1$ for $S_{2}$ and $5 / 4$ for $S_{3}$ ; the minimum $1$ is attained by both $S_{1}$ and $S_{2}$ , and the input-order tie rule selects $S_{1}$ , which charges $2 / 2 = 1$ to each of the elements $1$ and $2$ . With $r = 2$ elements ${3, 4}$ uncovered, the ratios are $2 / 2 = 1$ for $S_{2}$ and $5 / 2$ for $S_{3}$ ; the algorithm selects $S_{2}$ and charges $1$ to each of $3$ and $4$ . The uncovered set is then empty, so the algorithm stops with cover ${S_{1}, S_{2}}$ of total cost $4 = O P T$ .

3.1F2F3step 2.1algebra

At the first round $r = 4$ and the chosen price $1$ satisfies $1 \leq O P T / 4 = 1$ ; at the second round $r = 2$ and $1 \leq O P T / 2 = 2$ . Ordering the elements by first coverage, ties by input order, gives $1, 2, 3, 4$ , so the four charges are all $1$ and satisfy $1 \leq O P T / (4 - j + 1)$ for $j = 1, 2, 3, 4$ , namely $1 \leq 4 / 4$ , $1 \leq 4 / 3$ , $1 \leq 4 / 2$ , $1 \leq 4 / 1$ ; the first of these is an equality and the other three are strict. The sum of the charges is $4 \leq H_{4} O P T = (25 / 12) \cdot 4 = 25 / 3$ by [F3].

4.1F2step 3.1algebra∎

Thus the total greedy cost here equals the optimum $4$ , the pointwise charge bound of [F2] holds at each element with the remaining count actually in force, and the harmonic bound $H_{4} O P T = 25 / 3$ is strictly larger than both the greedy cost and the optimum; the example also shows the two bound forms at work: the per-round bound $O P T / r$ uses the remaining count $r$ of that round, while the per-element bound $O P T / (n - j + 1)$ is the index-based consequence.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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 Algorithm 1.2 and Theorem 1.11, printed pp. 25–26 (standard reference, not scraped)