04.10

Somebody asked this on Theory stack exchange and then deleted the question after I answered it (I assume it is a standard homework problem). Since I liked the problem, here is the question and answer.

Given a set system \((S,F)\) with \(n = |S|\) elements, and \(m=|F|\) sets, consider the algorithm that starts with all the elements having weight \(1\). At every iteration, the algorithm picks the heaviest set (taking into account the weight of all the elements – not only the uncovered ones as in the standard greedy algorithm). Next, the algorithm doubles the weight of all the uncovered elements. Question: What is the approximation quality of this algorithm?

The answer:

The trick is to divide the weight of the covered elements in every iterations instead of multiplying the weight of the uncovered elements. Clearly, up to a scaling by a factor of two, the two operations are equivalent, and in particular this preserve the relative order of the sets. Observe, that an uncovered element has weight \(1\) till it is covered for the first time. In particular, let \(W_0 = |n|\), and let \(W_i\) be the total weight of \(S\) in the beginning of the \(i\)th iteration. Let \(x_i\) be the weight of the set picked in the \(i\)th iteration, and observe that \(x_i \geq W_i/k\), where \(k\) is the number of sets in the optimal solution. Furthermore, \(W_{i+1} \leq W_i – x_{i}/2 \leq (1-1/2k) W_i\), as the weight of the elements of the set covered in the \(i\)th iteration get their weight halved. We conclude that \(W_{O(k \log n)} <1\), which implies that all the elements are covered in the end of the \(O( k \log n)\) iteration. Thus, this is \(O( \log n)\) approximation.