9.3.2. A Family of Tight Inputs

The following is a family of tight inputs that proves that the algorithm does not achieve an approximation factor better than \(f\). Consider an \(f\)-partite hypergraph \(G\). The vertex set of \(G\) is \(V = \{v_{i,j} \mid 1 \le i \le f, 1 \le j \le n\}\). The hyperedge set is \(E = \{\{v_{1,j_1}, \ldots, v_{f,j_f}\} \mid (j_1, \ldots, j_f) \in \{1, \ldots, n\}^f\}\). See Figure 9.10.

Figure 9.10: Coming soon!

We obtain a set cover instance by setting \(U = E\) and \(\mathcal{S} = \{ S_v = \{ e \in E \mid v \in e \} \mid v \in V \}\). The weight of every set \(S_v\) is \(1\). Every element \(e = \{v_{1,j_1}, \ldots, v_{f,j_f}\} \in U\) occurs in exactly the sets \(S_{v_{1,j_1}}, \ldots, S_{v_{f,j_f}}\) and therefore has frequency \(f\). Each set \(S_{v_{i,j}}\) contains all hyper-edges \({v_{1,j_1}, \ldots, v_{f,j_f}}\) such that \(j = j_i\). There are \(n^{f-1}\) such edges. Thus, the weight function satisfies \(w_S = \frac{|S|}{n^{f-1}}\), that is, it is degree-weighted, where \(\alpha = \frac{1}{n^{f-1}}\). The algorithm thus chooses \(\mathcal{S}\) as a set cover of weight \(fn\). An optimal set cover is \(\{v_{1,1}, \ldots, v_{1,n}\}\) because every hyperedge contains one such vertex \(v_{1,j}\) and thus is contained in the corresponding set \(S_{v_{1,j}}\). This set cover has weight \(n\). Thus, the set cover \(\mathcal{S}\) computed by the algorithm has weight \(f \cdot \textrm{OPT}\).