Set Cover / using Markov to bound the cost

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

Proof of theorem.

To prove the theorem, we show that the algorithm keeps the following pessimistic estimator (on the probability of failure) from increasing:

\[ \phi _ t ~ \doteq ~ \frac{\sum _{s\in S_ t} c_ t ~ +~ (T-t)c\cdot x/|x|}{2\, T\, c\cdot x/|x|} {\, {+}\, }n_ t(1-1/|x|)^{T-t}, \]

where S_ t contains the first t sets chosen and n_ t is the number of elements left uncovered by S_ t.


MathJax is loading, equations are not yet displayed...