Motivation
A locally efficient purchase need not produce the cheapest complete solution. Set cover makes that tension precise: one set can cover many still-uncovered requirements, but buying it can leave awkward requirements that are expensive to finish. Approximation analysis does not pretend that this difficulty disappears. It proves that a specified feasible output costs at most a controlled multiple of the optimum.
Three analyses will be developed on the same model. Greedy charges each requirement when it is first covered. Linear programming allows fractional purchases and supplies lower bounds. A primal–dual algorithm constructs a cover and a lower-bound certificate together. Their approximation factors arise from different structural parameters, so one should compare the guarantees as well as the algorithms.
Definitions
Definition 4.3.1
(Weighted set cover and its parameters)
Let be a finite universe with elements, and let be available subsets whose union is . Set has nonnegative finite cost . A cover is a selection whose union is ; its cost is the sum of selected costs. Write for the minimum cover cost. Let and let be the maximum number of available sets containing any one element. Feasibility ensures .
Sets are treated as labeled choices, so distinct available sets may have equal contents. Repetition in a selected solution is unnecessary because costs are nonnegative. Empty sets can be ignored. Zero-cost sets are permitted, and bounds will be written as inequalities rather than dividing by an optimum that might be zero. For computational claims, rational costs and an explicit incidence representation are natural inputs; the approximation proofs themselves use only exact finite arithmetic.
Greedy maintains an uncovered set . Among sets with , it selects one minimizing , then removes its newly covered elements from . Any fixed tie rule is valid. There is always an eligible set until completion, and each selection covers something new, so at most selections occur. Counting all elements of a set, including already covered ones, would define a different algorithm.
Definition 4.3.2
(Fractional cover and dual packing)
The fractional covering program minimizes subject to
Its dual packing program maximizes subject to
Replacing the fractional sign constraints by gives the exact integer-programming formulation. An integral cover supplies such a feasible – vector . A feasible dual assigns nonnegative prices to elements without overpricing any available set.
No strong-duality theorem is needed below. We will prove the lower-bound property directly. Computing an optimal fractional solution is a separate optimization task: the rounding theorem assumes such a solution has been supplied and does not implement a linear-programming solver.
Concept lensAlgebraic
The two parameters as row and column sums
Let be the - incidence matrix with when . Then is the largest column sum and the largest row sum. The primal program is subject to , and the dual is subject to .
Theorems
Theorem 4.3.3
(Harmonic greedy approximation)
Let . Greedy produces a cover of cost at most , hence at most . More strongly, its cost is at most times the fractional optimum.
Theorem 4.3.4
(Frequency rounding and a primal–dual algorithm)
For any feasible fractional cover , selecting every set with gives a cover of cost at most . There is also an algorithm that directly constructs a cover and a feasible dual , with cover cost at most , without first solving the fractional program.
Proof sketch or proof idea
Proof
(Weak duality)
First prove weak duality. For any feasible fractional cover and feasible dual , nonnegativity and the two families of constraints give
The middle equality rearranges a finite sum over incidences. Thus every feasible dual value is a lower bound for every cover cost. This is a certificate one can check by simple inequalities, even without knowing an optimum.
Charging greedy purchases
Proof
(Greedy by charging and weak duality)
When greedy selects a set covering new elements at cost , give each of those elements a charge . Each element is charged once, and the sum of all charges equals exactly the total selected cost. Sets may overlap; the charging rule prevents those overlaps from producing multiple payments for the same element in this accounting.
Fix any available nonempty set of size , not necessarily one selected. Order its elements by their first covering times, breaking ties within a single greedy selection arbitrarily. Before the selection covering its th element, at least elements of are still uncovered. The set was an eligible alternative at that moment, so greedy's chosen ratio and the element's charge satisfy
Summing yields . Consequently is a feasible dual vector for every set constraint, including empty ones. Weak duality now gives
where is the fractional optimum. The final inequality holds because integral covers form a subset of fractional feasible solutions in a minimization problem. One may equivalently compare to any fractional feasible cost, avoiding an existence assumption; an optimum does exist here because coordinates can be capped at one without harming feasibility or increasing cost, leaving a compact feasible region.
Since , the weaker statement follows. For , monotonicity of gives . Summing proves . This is a worst-case guarantee, not an assertion that every greedy output reaches the bound. If the optimum is zero, the same nonnegative inequalities force greedy's cost to be zero too.
Threshold rounding uses frequency, not set size
Proof
(Threshold rounding covers every element)
Let be a feasible fractional cover and fix an element . It occurs in at most sets. If all their coordinates were strictly below , their sum would be strictly below one, contradicting its covering constraint. Thus at least one containing set is selected by the threshold rule. This proves feasibility for every element.
For each selected , , so . Summing over selected sets and then using nonnegative costs to add the unselected terms gives the cost bound. Note the non-strict threshold: excluding coordinates equal to could leave an element uncovered. A fractional solution of large cost remains roundable, but only an optimal or approximately optimal fractional solution provides the corresponding comparison with an integer optimum.
The parameters and measure different things. A set may contain many elements while each element belongs to only two sets, or every set may be tiny while one element occurs many times. The harmonic guarantee is controlled by maximum set size; threshold rounding and the direct construction below are controlled by maximum element frequency. Neither parameter can silently replace the other in a proof.
Raising dual prices while building a cover
Proof
(Primal–dual construction)
Start with and no selected sets. While an uncovered element remains, increase only until a set containing becomes tight, meaning its total element price equals its cost. Select one such set and mark all its elements covered. If an eligible set is already tight, select it with no increase. Zero-cost sets therefore cause no division or progress problem.
To see that the increase is well defined, compute the nonnegative slack of every set containing . Increase by their minimum. There is at least one such set, all costs are finite, and every constraint not containing is unchanged. Containing constraints lose exactly that much slack, so none becomes negative. Dual feasibility is preserved and at least one eligible constraint becomes tight.
Previously selected sets contain no currently uncovered element. Therefore raising never changes their sums, and every selected set remains tight until termination. Each iteration covers at least one new element, giving at most selections. At completion,
The proof needs only feasible prices, tight selected constraints, and the frequency bound. It never asserts that the generated dual is optimal. Removing redundant selected sets afterwards can decrease cost, but is not required for the guarantee.
Proof X-ray
Two certificates with opposite inequality directions
A feasible cover bounds the optimum from above and a feasible dual bounds it from below; each analysis links the first to a controlled multiple of the second, but the hypotheses enter in different places. Greedy needs every set to have been an eligible alternative at each earlier step, which gives , and it then rescales by to restore dual feasibility. The primal–dual construction keeps feasibility at every step by raising one price only up to the smallest slack, and it keeps selected sets tight because only prices of uncovered elements ever change. The key move in its final computation is to exchange the order of summation over sets and elements: tightness turns the cost into , and the frequency bound turns that count into the factor . Nonnegativity of costs and prices is used in every inequality; without it the comparison with breaks.
Worked examples
Worked example 4.3.5
(Greedy can pay three when two suffice)
Take and unit-cost sets , , . Greedy first chooses , with ratio instead of . Elements five and six then force and , for cost three. Yet alone cover everything at cost two, and both are necessary because five occurs only in and six only in . Dual prices and all others zero certify the lower bound two. Local efficiency did not preserve exact optimality.
Worked example 4.3.6
(A fractional triangle and a rounding gap)
Let and let the three two-element subsets each cost one. An integral cover needs two sets. Assigning to each set gives fractional cost , while is dual feasible with the same value. Weak duality proves that fractional value is optimal. Here , so threshold rounding selects all three sets and costs three, exactly twice the fractional value, though the integer optimum is only two. Different valid algorithms can produce different quality on one instance.
Worked example 4.3.7
(A direct primal–dual run on the triangle)
On the same three-element instance, start with all prices zero. Choose uncovered and raise its price to one. The sets and become tight; choose . Only remains uncovered, but is already tight, so select it without changing prices. The cover costs two; the feasible dual has value one. The certified factor-two inequality holds, although this particular integral output is optimal. The dual need not be optimal for the algorithm's proof to succeed.
Counterexample mode
Thresholds cannot be rounded upward casually
In the fractional triangle, every coordinate is exactly . Selecting only coordinates strictly greater than chooses no sets and covers nothing. The repair is the proved rule , including equality. Floating-point tolerances require a separately justified feasibility repair; a mathematical threshold proof does not certify an arbitrary numerical implementation.
Common mistakes
Common mistake
(Reversing the direction of a relaxation bound)
A minimization relaxation gives a lower bound; a maximization relaxation gives an upper bound. Reversing that direction invalidates a ratio proof. Feasible dual prices also require every set inequality, not only constraints for selected sets. Greedy's unscaled charges generally violate some constraints, which is exactly why the harmonic scaling is needed.
Common mistake
(Raising the price of an already covered element)
The primal–dual proof relies on never raising the price of an already covered element. Doing so could destroy tightness of a previously selected set or violate its constraint. Overlap is harmless only because its multiplicity is explicitly bounded by in the final sum. No assumption of disjoint selected sets is made.
Summary
Charging converts greedy ratios into a dual-feasible lower-bound certificate after harmonic scaling. Frequency rounding turns any fractional cover into an integral one. The direct primal–dual method preserves feasibility and tightness throughout construction. Together these arguments show how local choices, relaxations, and lower bounds can produce rigorous approximation guarantees without claiming exact optimization.
Exercises
Quick check
(If every available set has at most three elements, state the harmonic guarantee explicitly and compare it with the bound based on the entire universe size.)
Compute and note that .
Solution · Answer
, so the greedy cost is at most times optimum, or the still smaller if . This is never worse than because . A universe can be large even though its sets are small.
Quick check
(In the fractional triangle, explain why the proposed dual is invalid, despite being nonnegative.)
Check the constraint of one two-element set.
Solution · Answer
Each two-element set would have total price two, exceeding its cost one. Nonnegative prices satisfy only the sign constraints; all set upper bounds are necessary. Scaling these prices to one half gives the feasible optimal dual in the example.
Quick check
(Model weighted vertex cover of a finite loopless graph as set cover and deduce a factor-two threshold-rounding guarantee. Handle isolated vertices and the case of no edges.)
Choose the universe, the sets and their costs, then find the frequency .
Solution · Answer
Use edges as universe elements and one available set per vertex, containing its incident edges and costing the vertex's nonnegative weight. Every edge belongs to exactly two vertex sets, so . A fractional vertex cover assigns endpoint values summing to at least one on every edge. Selecting all vertices of value at least one half covers every edge and costs at most twice the fractional objective. Isolated vertices contribute empty sets and need not be selected; if there are no edges, the empty selection is already an optimal cover of cost zero, handled separately from the chapter's convention.
Quick check
(Suppose every cost is zero on a feasible set-cover instance. Explain termination and the objective bound for greedy and the primal–dual construction.)
Look at the greedy ratio and the tight constraints when every cost is zero.
Solution · Answer
Greedy always chooses ratio zero among eligible sets and covers a new element each step, so it terminates within selections at cost zero. All primal–dual constraints are tight at the zero price vector. Each iteration selects a containing tight set with no price increase and covers something new, also terminating at zero cost. The inequalities remain meaningful even though dividing by OPT would not be valid.