# Greedy Set Cover III: weighted H(d)-approximation via localizing

Strengthening the approximation ratio to by “localizing” the analysis.

Applying the -approximation result to the “local” subproblem for each set strengthens the approximation ratio to , where is the maximum set size, matching the classical bound

# Localized rounding scheme for Set Cover

 input: weighted Set-Cover instance output: set cover for 0. Compute a min-cost fractional set cover . 1. Repeat until the chosen sets form a cover: 2. Choose a set randomly from the distribution defined by . 3. Return the sets that, when chosen, contained not-yet-covered elements.

Note that the localized rounding scheme returns only “useful” sets.

Lemma.

The localized rounding scheme returns a cover of expected cost at most , which is at most , where is the maximum set size.

Proof.

For any set , define to be the weighted Set Cover instance obtained from by deleting all elements other than those in , giving cost 1, and giving all other sets cost 0. By the analysis of the original (non-localized) rounding scheme, if we apply that rounding scheme to (with fractional solution ), the probability that is chosen is at most .

Since that rounding scheme chooses with exactly the same probability that the localized rounding scheme chooses , the probability that the localized rounding scheme puts in the final cover is also at most . By linearity of expectation, summing over the sets, the expected cost of the cover returned by the localized scheme is at most .

Next we apply the method of conditional probabilities to obtain the following algorithm.

# Greedy algorithm for Set Cover (weighted): H(d)-approximation via localization

 input: weighted Set-Cover instance output: set cover for 1. Repeat until the chosen sets form a cover: 2. Choose a set minimizing the cost of divided by the number of elements in not yet covered by chosen sets. 3. Return the chosen sets.

To apply the method of conditional probabilities, we need a pessimistic estimator for the cost of the final cover. Following the existence proof, we simply sum the pessimistic estimators for the individual sets, where for each set we use the pessimistic estimator for the original, non-localized rounding scheme for ’s subproblem :

$\phi _ t ~ =~ \sum _ s c_ s\, \phi ^ s_ t ~ =~ \sum _ s c_ s\big ({\rm H}(n^ s_ t) x^*_ s ~ +~ [s\in S_ t]\big ),$

where contains the sets that were sampled in the first iterations and, when sampled, contained not-yet-covered elements, while is the number of elements in not covered by the end of iteration . (Note for .)

The algorithm keeps the pessimistic estimator from increasing at each step. A slightly refined variant of Chvátal’s performance guarantee follows as a corollary:

Theorem ([1]).

The algorithm above returns a cover of cost at most , where is any fractional set cover. This is at most , where is the maximum set size and is the minimum cost of any fractional cover.