Using the Markov bound on the cost yields an ugly greedy algorithm.
As illustrated in a previous note, one can use random stopping times and Wald’s equation to bound the cost, leading to Chvatal’s algorithm. Here we describe another approach: analyzing a fixed number of samples, then using the Markov bound to bound the cost. This leads to a more complicated algorithm with a slightly weaker approximation ratio.
Ugly algorithm
We show the following performance guarantee:
The algorithm below is a 2(1+\ln (2n))-approximation algorithm.
input: collection S of sets, costs c: S\rightarrow {\mathbb R}_+ | |
output: set cover C | |
1. | Let T\doteq \lceil \ln (2n) n\rceil . |
2. | For t=1,2,\ldots ,T do: |
3. | Let set U contain the elements not yet covered by chosen sets. |
4. | Define \mbox{rhs}(s) \doteq \frac{1}{2T} + |U|(1-1/n)^{T-t+1} – |U-s|(1-1/n)^{T-t}. |
5. | If \mbox{rhs}(\emptyset ) \ge 0 do nothing (i.e., choose s=\emptyset ). |
6. | Else, choose a set s to maximize \mbox{rhs}(s)/c_ s. |
7. | Return the chosen sets. |
To prove the theorem we apply the method of conditional probabilities to the usual rounding scheme. We start by analyzing the rounding scheme.
Fix T\doteq \lceil \ln (2n)|x| \rceil . With positive probability, the rounding scheme returns a cover C of cost at most 2 T c\cdot x /|x| (which is at most 2(1+\ln (2n))c\cdot x).
Method of conditional probabilities
To prove the theorem, we show that the algorithm keeps the following pessimistic estimator (on the probability of failure) from increasing:
where S_ t contains the first t sets chosen and n_ t is the number of elements left uncovered by S_ t.