9.2.3. A Family of Tight Inputs

The following is a family of tight inputs that shows that the algorithm does not achieve an approximation ratio better than \(\frac{H_n}{1+\epsilon}\) for any \(\epsilon > 0\): For an arbitrary \(n\), an input where the algorithm achieves an approximation ratio of exactly \(\frac{H_n}{1+\epsilon}\) consists of a universe \(U = \{1, \ldots, n\}\) and \(n+1\) sets \(S_1, \ldots S_{n+1}\). For \(1 \le i \le n\), the \(i\)th set is \(S_i = \{i\}\) and has weight \(w_{S_i} = \frac{1}{n-i+1}\). The \((n+1)\)st set is \(S_{n+1} = \{1, \ldots, n\}\) and has cost \(w_{S_{n+1}} = 1 + \epsilon\). See Figure 9.9.

Figure 9.9: Coming soon!

The optimal set cover covers \(U\) using \(S_{n+1}\). The cost of this set cover is \(1 + \epsilon\). However, the greedy algorithm runs for \(n\) iterations on this input and picks the set \(S_i\) in the \(i\)th iteration. Indeed, after picking sets \(S_1, \ldots, S_{i-1}\) in the previous \(i-1\) iterations, the set \(S_i\) has amortized cost \(\frac{1}{n-i+1}\) because the only element \(i \in S_i\) is not covered by \(S_1, \ldots, S_{i-1}\). Any set \(S_j\) with \(i < j \le n\) has amortized cost \(\frac{1}{n-j+1} > \frac{1}{n-i+1}\). The set \(S_{n+1}\) has amortized cost \(\frac{1 + \epsilon}{n - i + 1} > \frac{1}{n - i + 1}\) because the elements \(1, \ldots, i-1\) are already covered by \(S_1, \ldots, S_{i-1}\). Thus, the \(i\)th iteration picks the set \(S_i\). The set cover computed by the greedy algorithm is thus \({S_1, \ldots, S_n}\), which has cost \(\sum_{i=1}^n \frac{1}{n - i + 1} = H_n = \frac{H_n}{1 + \epsilon} \cdot \textrm{OPT}\).