# 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:

Theorem.

The algorithm below is a -approximation algorithm.

 input: collection of sets, costs output: set cover 1. Let . 2. For do: 3. Let set contain the elements not yet covered by chosen sets. 4. Define . 5. If do nothing (i.e., choose ). 6. Else, choose a set to maximize . 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.

Lemma.

Fix . With positive probability, the rounding scheme returns a cover of cost at most (which is at most ).

# 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 contains the first sets chosen and is the number of elements left uncovered by .