# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Covering Problems
#### 4.2.2 Maximization Variants  
We now move on to the maximization variants of covering problems. To our knowledge, these covering problems are much less studied in the context of parameterized approximability compared to their minimization counterparts. In particular, we are only aware of works on the maximization variants of Set Cover and Vertex Cover, which are typically called Max \(k\)-Coverage and Max \(k\)-Vertex Cover respectively. Max \(k\)-Coverage.Recall that here we are given a set system and the goal is to select \(k\) subsets whose union is maximized. It is well known that the simple greedy algorithm yields an \(\big{(}\frac{\varepsilon}{\varepsilon-1}\big{)}\)-approximation [142]. Furthermore, Fiege shows, in his seminal work [29], show that this is tight: \((\frac{\epsilon}{\epsilon-1}-\epsilon)\)-approximation is NP-hard for any constant \(\epsilon>0\). In fact, recently it has been shown that this inapproximability applies also to the parameterized setting. Specifically, under Gap-ETH, \(\big{(}\frac{\epsilon}{\epsilon-1}-\epsilon\big{)}\)-approximation cannot be achieved in FPT time [143] or even \(f(k)\cdot n^{o(k)}\) time [70]. In other words, the trivial algorithm is tight in terms of running time, the greedy algorithm is tight in terms of approximation ratio, and there is essentially no trade-off possible between these two extremes. We remark here that this hardness of approximation is also the basis of hardness for \(k\)-Median and \(k\)-Means[143] (see Section 4.3). Due to the strong inapproximability result for the general case of Max \(k\)-Coverage, different parameters have to be considered in order to obtain a PAS for Max \(k\)-Coverage. An interesting positive result here is when the parameters are \(k\) and the VC dimension of the set system, for which a PAS exists while the exact version of the problem is W[1]-hard [144]. Max \(k\)-Vertex Cover.Another special case of Max \(k\)-Coverage is the restriction when each element belongs to at most \(d\) subsets in the system. This corresponds exactly to the maximization variant of the Vertex Cover problem on \(d\)-uniform hypergraph, which will refer to as Max \(k\)-Vertex Cover. Note here that, for such set systems, their VC-dimensions are also bounded by \(\log d+1\) and hence the aforementioned PAS of [144] applies here as well. Nonetheless, Max \(k\)-Vertex Cover admits a much simpler PAS (and even PSAKS) compared to Max \(k\)-Coverage parameterized by \(k\) and VC-dimension, as we will discuss more below. Max \(k\)-Vertex Cover was first studied in the context of parameterized complexity by Guo et al. [145] who showed that the problem is W[1]-hard. Marx, in his survey on parameterized approximation algorithms [8], gave a PAS for the problem with running time \(2^{\mathcal{O}(k^{3}/\epsilon)}\). Later, Lokshtanov et al. [18] shows that Marx's approach can be used to give a PSAKS of size \(O(k^{5}/\epsilon^{2})\). Both of these results mainly focus on graphs. Later, Skowron and Faliszewski [146; 147; 148] gave a more general argument that both works generally for any \(d\)-uniform hypergraph and improves the running time and kernel size:  
Theorem 2.1 ([146]): _For the Max \(k\)-Vertex Cover problem in \(d\)-uniform hypergraphs, a \((1+\epsilon)\)-approximation can be computed in \(O^{*}\left((d/\epsilon)^{k}\right)\) time for any \(\epsilon>0\). Moreover, an \((1+\epsilon)\)-approximate kernel with \(O(dk/\epsilon)\) vertices can be computed in polynomial time._  
The main idea of the above proof is simple and elegant, and hence we will include it here. For convenience, we will only discuss the graph case, i.e., \(d=2\). It suffices to just give the \(O(k/\epsilon)\)-vertex kernel; the PAS immediately follows by running the brute force algorithm on the output instance from the kernel. The kernel is as simple as it gets: just keep \(2k/\epsilon\) vertices with highest degrees and throw the remaining vertices away!