Strengthening the approximation ratio to {\rm H}(d) by “localizing” the analysis.
Applying the {\rm H}(n)-approximation result to the “local” subproblem for each set strengthens the approximation ratio to {\rm H}(d), where d=\max _ s |s| is the maximum set size, matching the classical bound
Localized rounding scheme for Set Cover
input: weighted Set-Cover instance {\cal I} | |
output: set cover for {\cal I} | |
0. | Compute a min-cost fractional set cover x^*. |
1. | Repeat until the chosen sets form a cover: |
2. | Choose a set randomly from the distribution defined by x^*/|x^*|. |
3. | Return the sets that, when chosen, contained not-yet-covered elements. |
Note that the localized rounding scheme returns only “useful” sets.
The localized rounding scheme returns a cover of expected cost at most \sum _ s c_ s\, x^*_ s\, {\rm H}(|s|), which is at most {\rm H}(d)~ c\cdot x^*, where d=\max _ s |s| is the maximum set size.
For any set s, define {\cal I}_ s to be the weighted Set Cover instance obtained from {\cal I} by deleting all elements other than those in s, giving s 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 {\cal I}_ s (with fractional solution x^*), the probability that s is chosen is at most {\rm H}(|s|) x^*_ s.
Since that rounding scheme chooses s with exactly the same probability that the localized rounding scheme chooses s, the probability that the localized rounding scheme puts s in the final cover is also at most {\rm H}(|s|) x^*_ s. By linearity of expectation, summing over the sets, the expected cost of the cover returned by the localized scheme is at most \sum _ s c_ s\, {\rm H}(|s|)\, x^*_ s.
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 {\cal I} | |
output: set cover for {\cal I} | |
1. | Repeat until the chosen sets form a cover: |
2. | Choose a set s minimizing the cost of s divided by the number of elements in s not yet covered by chosen sets. |
3. | Return the chosen sets. |
To apply the method of conditional probabilities, we need a pessimistic estimator \phi _ t 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 s we use the pessimistic estimator \phi ^ s_ t for the original, non-localized rounding scheme for s’s subproblem {\cal I}_ s:
where S_ t contains the sets that were sampled in the first t iterations and, when sampled, contained not-yet-covered elements, while n^ s_ t is the number of elements in s not covered by the end of iteration t. (Note {\rm H}(n^ s_ t) = {\rm H}(0)=0 for s\in S_ t.)
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:
The algorithm above returns a cover of cost at most \sum _ s x^*_ s c_ s {\rm H}(|s|), where x^* is any fractional set cover. This is at most {\rm H}(d)~ c\cdot x^*, where d=\max _ s |s| is the maximum set size and c\cdot x^* is the minimum cost of any fractional cover.