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

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.

Lemma.

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.

\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=0.8in]{shared/graphics/set_cover_localized}  

Proof.

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:

\[ \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 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:

Theorem ([1]).

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.