Motivation
A fractional solution can distribute one unit of coverage among many sets, whereas an actual cover must choose whole sets. Independent random choices let the fractional values guide that decision. The essential tension is that a cheap random choice may miss an element, so we must control both expected cost and feasibility. Repeating the choices and explicitly repairing uncovered elements gives a complete algorithm rather than merely a high-probability suggestion.
Definitions
Definition 4.1.1
(Set cover and its fractional relaxation)
Let be a finite universe with elements, and let have costs . Assume every element belongs to at least one set. A cover is a collection whose union is . The fractional relaxation minimizes subject to for every and . Let be any feasible fractional solution and ; an optimal fractional solution is no more expensive than an optimal integral cover, because every integral cover supplies a feasible zero–one solution.
Definition 4.1.2
(Randomized rounding with repair)
Fix an integer . Independently for each set , choose it with probability . Equivalently, conduct independent trials with selection probability and retain the set if at least one succeeds. Afterward, for each uncovered element add a cheapest set containing it. Duplicates are paid for only once. The repair is well-defined by the coverability assumption.
Theorems
Theorem 4.1.3
(Coverage and cost of rounding with repair)
The algorithm always returns a cover, and its expected cost is at most . In particular, choosing for gives expected cost at most , and hence at most that factor times the optimum integral cover when is an optimal fractional solution. For , gives the bound .
Theorem 4.1.4
(High-probability coverage before repair)
For any feasible fractional solution, the probability that at least one element is uncovered after the random choices is at most . In particular, for , taking makes this probability at most .
Proof sketch or proof idea
Proof
(Union bound, linearity and the repair charge)
For a fixed element , independent set choices give
Here for ; the formula also covers . Summing these probabilities over all elements proves the union bound. No independence between the events for different elements is needed.
The probability that set is selected is at most , by the union bound over its trials. Linearity of expectation therefore bounds initial cost by , regardless of overlaps among sets. Let be the cost of a cheapest set containing . Since all such costs are at least , fractional feasibility gives
The actual repair cost is at most , where indicates that was initially uncovered; this remains an upper bound even if one added set repairs several elements. Taking expectations gives at most . Adding the two bounds proves the theorem. Repair makes feasibility certain; the expected-cost guarantee is not a deterministic bound on every outcome.
Proof X-ray
Two uses of linearity
Expected cost sums over sets, while expected repair cost sums over elements. Neither calculation requires those cost terms to be independent. Independence is used earlier, to factor the probability that all sets containing one fixed element are missed.
Worked examples
Worked example 4.1.5
(A triangle of sets)
Let with unit-cost sets , and . Setting each is feasible with . With , each set is chosen with probability . Each element is missed with probability . The expected initial cost is ; the general repair bound is , since each cheapest covering set costs one. Thus expected total cost is at most . The true optimum integral cost is .
Worked example 4.1.6
(A forced choice)
If element lies in exactly one set , feasibility and force . The rounding chooses with probability one for every positive . Treating each element as having failure probability exactly would be an error: that is a uniform upper bound, not an equality.
Worked example 4.1.7
(Choosing a failure target)
For and , suffices. The probability of any uncovered element before repair is at most . Repair then gives a cover on every run. The theorem controls expected cost; it does not assert that every run costs at most .
Common mistakes
Counterexample mode
Rounding each fraction once can fail
In the triangle example with one trial, the probability that both sets containing element are absent is . Thus independent rounding of a feasible LP solution does not automatically produce a cover. Repetition reduces the failure probability and repair eliminates the remaining feasibility risk.
Common mistake
(Expected cost is not a guarantee for each run)
Expected cost and failure probability are separate statements. A small expected cost alone does not ensure that a particular run is cheap, and a small failure probability does not make an uncovered outcome feasible. Also, the LP lower bound requires a minimization problem and nonnegative costs as specified; the direction of an approximation guarantee must be checked against that lower bound.
Why the logarithm appears
For a single element the bound decreases exponentially with the number of independent trials. To make all elements simultaneously likely to be covered, the union bound multiplies this by . Choosing on the scale of offsets that factor. This is the source of the logarithm in the proof; it is not a claim that each particular instance needs that many trials. In the forced-choice example one trial covers the special element with certainty. The union bound treats all elements as if each had the worst allowed failure probability and can be quite loose.
The LP also provides a numerical certificate useful before running the rounding. For any integral cover, putting for chosen sets and for the others gives a feasible fractional point of the same cost. Therefore any lower bound on the fractional optimum is a lower bound on the cost of every integral cover. An arbitrary feasible fractional point, however, is an upper bound on the fractional optimum, not automatically a lower bound on the integral optimum. The approximation comparison with the integral optimum therefore uses an optimal fractional solution (or a separately justified approximation to one); the cost bound relative to holds for every feasible fractional point.
Worked example 4.1.8
(Feasible fractional does not mean optimal)
Let and take two sets, both equal to , with costs and . The choice is fractional-feasible and has , while the optimum integral and fractional costs are both . The rounding theorem still bounds expected cost in terms of , but substituting would be false. Choosing an optimal LP solution repairs the comparison.
Independence, repair, and implementation
One implementation draws a single independent Bernoulli variable of probability per set. The equivalent repeated-trials description is a proof device and a way to implement the same distribution: trials belonging to different sets must all be independent. The events that two elements are uncovered generally are not independent, because the same randomly chosen set may contain both. The union bound deliberately avoids needing their joint distribution. For instance, if a single set contains both elements, failure to select it makes both uncovered together.
Repair can be implemented by scanning the universe after the random selections, then adding a cheapest available containing set for each element that remains uncovered. The proof charges at most for every element initially uncovered. If an earlier repair also covers a later element, that later charge may be unnecessary, but charging it anyway preserves an upper bound. Thus the analysis does not depend on the order of repairs. Nonnegative costs ensure that counting an added set multiple times cannot underestimate the real cost; duplicates can be stored only once.
The idealized proof assumes exact probabilities and an optimal LP solution. In an actual implementation one must specify the arithmetic, solver tolerance, and random-bit model. A feasible approximately optimal fractional vector can still be rounded using the same proof, with its actual objective value ; to obtain a stated approximation factor relative to the integral optimum one also needs a proved bound on that value. Rounding an approximately feasible vector without correcting constraint violations does not justify the estimate: the sum of incident fractions must be at least one for every element as assumed.
The repair estimate can be refined to rather than . This sharper form follows directly from linearity and may be much smaller on a particular instance. The coarser bound makes the approximation factor depend only on and the LP value. For instance, if all elements have access to a cheap set but the fractional solution also pays for other expensive sets, can be substantially below .
A useful probability calculation
When an explicit failure threshold matters, the probability bound should be used with the correct direction. For example, if and the desired upper bound is , it suffices that . Taking the integer ceiling gives , and . This is a sufficient choice, not a proof that thirteen trials are impossible on a particular instance. The actual probability can be much smaller because fractional constraints may be slack or because failure events overlap strongly.
A separate Markov bound can turn the expectation statement into a tail statement for cost. Since total cost is nonnegative, for any , . Thus with probability at least , the repaired cover costs at most , interpreting the boundary harmlessly. This conclusion is weaker than an expected-cost guarantee in its constant, but it supplies a probability for one run. If , nonnegative cost and the expectation bound imply cost zero almost surely, so the conclusion also holds without applying Markov at a zero threshold. Independent repetitions can reduce the chance that all runs exceed the threshold; selecting the cheapest repaired cover preserves feasibility. Independence between repetitions must be arranged, and the cost of generating them must be counted in an implementation.
A deterministic check on the random outcome
Once the random choices have been made, no probability calculation is needed to check whether the output is a cover. Scan the selected sets, mark every element they contain, and verify that all elements are marked. The repair step guarantees this check will succeed provided that the input satisfies the coverability assumption and the cheapest containing sets are found correctly. If an input element lies in no available set, the original instance has no feasible cover and its fractional constraints are also infeasible; the repair theorem intentionally excludes that case.
Common mistake
(Two different comparisons in one approximation claim)
The approximation statement has two distinct comparisons. First, the mathematical expectation of the output cost is bounded by a multiple of the objective value of the fractional point supplied to rounding. Second, an optimal fractional value is bounded above by the minimum integral cover cost. The second comparison uses the containment of feasible sets: all integral covers produce fractional feasible points, while the relaxation may have additional fractional points. Confusing which feasible set is larger reverses the conclusion. A fractional optimal value may be strictly smaller, as in the triangle example where it is at most one and a half while the cheapest integral cover costs two.
The random selection rule also has an intuitive limiting case. When a fractional variable is zero, its set is never selected during rounding, although repair can still add it if it is cheapest for an uncovered element. When a variable is one, its set is selected with certainty. For intermediate values, the probability increases with the number of trials but never exceeds one. Using directly as a probability would fail whenever that number exceeds one. It remains valid as an upper bound on the actual probability, which is exactly how the expected-cost proof uses it.
The theorem assumes nonnegative costs. If negative-cost sets were permitted, selecting an extra set could reduce total cost and repeatedly charging a set could reverse an inequality in the repair argument. One could preprocess such a different model by selecting negative-cost sets first and modifying the instance, but that would require a separate analysis. Here the nonnegative-cost hypothesis lets every partial sum be bounded by the full fractional objective and makes the repair-cost comparison transparent.
Summary
Randomized rounding converts fractional membership into independent set choices. Exponential decay bounds the chance of missing one element; a union bound controls all elements, while a cheapest-set repair yields certain feasibility and a logarithmic expected approximation bound.
Exercises
Quick check
(In the triangle example, calculate the probability that no set is selected when .)
Each set is missed with the same probability.
Solution · Answer
Each set is absent with probability , independently, so the probability is .
Quick check
(If and , give the union-bound upper bound on the chance of any uncovered element.)
Use the bound from the high-probability theorem.
Solution · Answer
It is at most . The bound need not be tight.
Quick check
(Why can one sum the expected costs of selected sets even if the events that elements are covered are dependent?)
Which property of expectation needs no independence?
Solution · Answer
Linearity of expectation holds without independence. Independence of set choices is used to bound the probability of missing a fixed element, not to add expected costs.
Quick check
(Suppose and is optimal for the fractional relaxation. Give the theorem's expected approximation factor for .)
Substitute and into .
Solution · Answer
The bound is . Since the fractional optimum is at most the integral optimum, the same number is an expected approximation factor.