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

Click for background material…

Set Cover (weighted): H(n)-approximation via random stopping time

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$ .)

Click for verification of the pessimistic estimator…

1. The pessimistic estimator is initially $\sum _s c_s x^*_s {\rm H}(|s|)$ . (By inspection.)

2. The pessimistic estimator is a super-martingale w.r.t. the localized rounding scheme.

This holds simply because the estimator is a sum of pessimistic estimators, each of which we already know is a super-martingale with respect to the original rounding scheme applied to ${\cal I}_s$ , and we know that scheme treats the set $s$ the same as the localized rounding scheme.

To verify, suppose iteration $t$ samples set $s'$ . Then, in the case that $n^t_{s'} = 0$ , the increase in the pessimistic estimator is zero. Otherwise, following the non-localized analysis, the increase is at most

$\begin{equation} \label{desired} c_{s'} \, -\, \sum _{s\, :\, n^s_t\gt 0} \frac{n^s_{t-1} - n^s_{t}}{n^s_{t-1}} c_s x^*_s. \end{equation}$

Recall that $\textrm{E}[n^s_{t-1} - n^s_t \, |\, n^s_{t-1}]$ is at least $n^{s}_{t-1}/|x^*|$ , while $\textrm{E}[c_{s'}] = \sum _s x^*_s c_s$ . Hence, in expectation \eqref{desired} is non-positive.

3. If the final value of the pessimistic estimator is at most its initial value, then the outcome is a success. (By inspection.)

Now that we’ve verified the pessimistic estimator, we verify that the algorithm keeps it from increasing at each step. The algorithm chooses a set $s'$ in iteration $t$ to minimize $c_{s'}/n^{s'}_t$ . Let $\tilde s$ contain the elements in $s'$ are not covered by sets in $S_t$ (so $|\tilde s| = n^{s'}_t$ ).

With this choice of $s'$ , the bound \eqref{desired} is

$\begin{align*} c_{s'} {\, {-}\, }\displaystyle \sum _{s\, :\, n^s_t\gt 0} \sum _{e\in \tilde s\cap s} c_s x^*_s / n^s_t ~ & =~ c_{s'} {\, {-}\, }\displaystyle \sum _{e\in \tilde s} \sum _{s\ni e} c_s x^*_s / n^s_t & (\text{as } n^s_t - n^s_{t+1} = |\tilde s\cap s|) \\ & {\, {\le }\, }~ c_{s'} {\, {-}\, }\displaystyle (c_{s'}/n_t^{s'}) \sum _{e\in \tilde s} \sum _{s\ni e} x^*_s & (\text{by the choice of } s') \\ & {\, {\le }\, }~ c_{s'} {\, {-}\, }\displaystyle (c_{s'}/n_t^{s'}) \sum _{e\in \tilde s} 1 & (\text{by the feasibility of } x) \\ & =~ 0 & (\text{as } |\tilde s| = n^{s'}_t). \end{align*}$

Thus, the algorithm keeps the pessimistic estimator from increasing.

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.

Bibliography

[1]	V. Chvátal. A greedy heuristic for the set-covering problem. Math. Operations Research, 4(3):233–235, 1979.

Notes on algorithms

Lecture notes on algorithms

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

Localized rounding scheme for Set Cover

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

Bibliography