# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Clustering
#### 4.3.1 General Metric Space
Fix an optimal solution, and let \(C^{*}=\{c_{1}^{*},\ldots,c_{k}^{*}\}\) are the optimal centers and \(P_{i}^{*}\subseteq P\) is the cluster assigned to \(c_{i}^{*}\). One information we can guess is, for each \(i\in[k]\), the point \(p_{i}\in P_{i}^{*}\) closest to \(c_{i}^{*}\) and (approximate) \(\rho(c_{i}^{*},p_{i})\). Since \(|P|=\operatorname{poly}(k\log n)\), guessing them only takes time \((k\log n)^{O(k)}\), which can be made FPT by separately considering the case \((\log n)^{k}\leq n\) and the case \((\log n)^{k}\geq n\), in which \(k=\Omega(\log n/\log\log n)\) and \((\log n)^{k}=(k\log k)^{O(k)}\). Let \(F_{i}\subseteq F\) be the set of candidate centers that are at distance approximately \(r_{i}\) from \(p_{i}\), so that \(c_{i}^{*}\in F_{i}\) for each \(i\). The algorithm chooses \(k\) centers \(C\subseteq F\) such that \(|C\cap F_{i}|\geq 1\) for each \(i\in[k]\). Let \(c_{i}\in C\cap F_{i}\). For any point \(p\in P\) (say \(p\in P_{j}^{*}\), though the algorithm doesn't need to know \(j\)), then  
\[\rho(C,p)\leq\rho(c_{j},p)\leq\rho(c_{j},p_{j})+\rho(p_{j},c_{j}^{*})+\rho(c_{ j}^{*},p)\leq 3\rho(c_{j}^{*},p),\]  
where \(\rho(c_{j},p_{j})\approx\rho(p_{j},c_{j}^{*})\leq\rho(c_{j}^{*},p)\) by the choice of \(p_{j}\). This immediately gives a 3-approximation algorithm in FPT time, which is worse than the best polynomial time approximation algorithm. To get the optimal \((1+2/e)\)-approximation algorithm, we further reduce the job of finding \(c_{i}\in F_{i}\) to maximizing a monotone submodular function with a partition matroid constraint, which is known to admit an optimal \((1-1/e)\)-approximation algorithm [162]. Then we can ensure that for \((1-1/e)\) fraction of points, the distance to the chosen centers is shorter than in the optimal solution, and for the remaining \(1/e\) fraction, the distance is at most three times the distance in the optimal solution. We refer the reader to [143] for further details. Constructing a coreset.As discussed above, a coreset is a fundamental building block for optimal parameterized approximation algorithms for \(k\)-Median and \(k\)-Means for general metrics. We briefly describe the construction of Chen [160] that gives a coreset of cardinality \(\widetilde{O}(k^{2}\log^{2}n/\varepsilon^{2})\) for \(k\)-Median. Similar ideas can be also used to obtain an EPAS for Euclidean spaces parameterized by \(k\), though better specific constructions are known in Euclidean spaces. We first partition \(P\) into \(P_{1},\ldots P_{\ell}\) such that \(\ell=O(k\log n)\) and  
\[\sum_{i=1}^{\ell}|P_{i}|\operatorname{diam}(P_{i})=O(\operatorname{Opt}).\]Such a partition can be obtained by using a known (bicriteria) constant factor approximation algorithm for \(k\)-Median. Next, let \(t=\widetilde{O}(k\log n)\), and for each \(i=1,\ldots,\ell\), we let \(S_{i}=\{s_{1},\ldots,s_{t}\}\) be a random subset of \(t\) points of \(P_{i}\) where each \(s_{j}\) is an independent and uniform sample from \(P_{i}\) and is given weight \(|P_{i}|/t\). (If \(|P_{i}|\leq t\), we simply let \(S_{i}=P_{i}\) with weights 1.) The final coreset \(S\) is the union of all \(S_{i}\)'s. To prove that it works, we simply need to show that for any set of \(k\) centers \(C\subseteq F\) with \(|C|=k\),  
\[\Pr[|\operatorname{cost}(S,C)-\operatorname{cost}(P,C)|>\varepsilon\cdot \operatorname{cost}(P,C)]\leq o(1/n^{k}),\]  
so that the union bound over \(\binom{n}{k}\) choices of \(C\) works. Indeed, we show that for each \(i=1,\ldots,\ell\),  
\[\Pr[|\operatorname{cost}(S_{i},C)-\operatorname{cost}(P_{i},C)|>\varepsilon \cdot|P_{i}|\operatorname{diam}(P_{i})]\leq o(1/(\ell\cdot n^{k})), \tag{1}\]  
so that we can also union bound and sum over \(i\in[\ell]\), using the fact that \(\sum_{i}|P_{i}|\operatorname{diam}(P_{i})=O(\operatorname{Opt})\leq O( \operatorname{cost}(P,C))\). It is left to prove (1). Fix \(C\) and \(i\) (let \(P_{i}=\{p_{1},\ldots,p_{|P_{i}|}\}\)), and recall that  
\[\operatorname{cost}(P_{i},C)=\sum_{j=1}^{|P_{i}|}\rho(C,p_{j}).\]  
When \(|P_{i}|\leq t\), \(S_{i}=P_{i}\), so (1) holds.