# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Clustering
#### 4.3.1 General Metric Space  
We can assume \(X=P\cup F\) without loss of generality. Let \(n:=|X|\) and note that the distance \(\rho:X\times X\to\mathbb{R}^{+}\cup\{0\}\) is explicitly specified by \(\Theta(n^{2})\) numbers. A simple exact algorithm running in time \(O(n^{k+1})\) can be achieved by enumerating all \(k\) centers \(c_{1},\ldots,c_{k}\in F\) and assign each point \(p\) to the closest center. In this setting, the best approximation ratios achieved by polynomial time algorithms are \(2.611+\varepsilon\) for \(k\)-Median[155], \(9+\varepsilon\) for \(k\)-Means[156], and \(3\) for \(k\)-Center[157; 158]. From the hardness side, it is NP-hard to approximate \(k\)-Median within a factor \(1+2/e-\varepsilon\approx 1.73-\varepsilon\), \(k\)-Median within a factor \(1+8/e-\varepsilon\approx 3.94-\varepsilon\), \(k\)-Center within a factor \(3-\varepsilon\)[159]. While there are some gaps between the best algorithms and the best hardness results for \(k\)-Median and \(k\)-Means, it is an interesting question to ask how parameterization by \(k\) changes the approximation ratios for both problems. Cohen-Addad et al. [143] studied this question and gave exact answers. **Theorem 22** ([143]). : _For any \(\varepsilon>0\), there is an \((1+2/e+\varepsilon)\)-approximation algorithm for \(k\)-Median, and an \((1+8/e+\varepsilon)\)-approximation algorithm for \(k\)-Means, both running in time \((O(k\log k/\varepsilon^{2}))^{k}n^{O(1)}\)._  
_There exists a function \(g:\mathbb{R}^{+}\to\mathbb{R}^{+}\) such that assuming the Gap-ETH, for any \(\varepsilon>0\), any \((1+2/e-\varepsilon)\)-approximation algorithm for \(k\)-Median, and any \((1+8/e-\varepsilon)\)-approximation algorithm for \(k\)-Means, must run in time at least \(n^{\text{\rm{R}}^{\varepsilon(\varepsilon)}}\)._  
These results show that if we parameterize by \(k,1+2/e\) (for \(k\)-Median) and \(1+8/e\) (for \(k\)-Means) are the exact limits of approximation for parameterized approximation algorithms. Similar reductions also show that no parameterized approximation algorithm can achieve \((3-\varepsilon)\)-approximation for \(k\)-Center for any \(\varepsilon>0\) (only assuming \(\text{W}[2]\
eq\text{FPT}\)), so the power of parameterized approximation is exactly revealed for all three objective functions. Algorithm for \(k\)-Median.We briefly describe ideas for the algorithm for \(k\)-Median in Theorem 4. The main technical tool that the algorithm uses is a coreset, which will be also frequently used for Euclidean subspaces in the next subsection. When \(S\) is a set of points with weight functions \(w:S\to\mathbb{R}^{+}\), let us extend the definition of the objective function \(\operatorname{cost}(S,C)\) such that  
\[\operatorname{cost}(S,C):=\sum_{p\in S}w(p)\cdot\rho(C,s).\]  
Given a clustering instance \((P,F,\rho,k)\) and \(\varepsilon>0\), a subset \(S\subseteq P\) with weight functions \(w:S\to\mathbb{R}^{+}\) is called a (strong) coreset if for any \(k\) centers \(C=\{c_{1},\ldots,c_{k}\}\subseteq F\),  
\[|\operatorname{cost}(S,C)-\operatorname{cost}(P,C)|\leq\varepsilon\cdot \operatorname{cost}(P,C).\]  
For a general metric space, Chen [160] gave a coreset of cardinality \(\widetilde{O}(k^{2}\log^{2}n/\varepsilon^{2})\). (In this subsection, \(\widetilde{O}(\cdot)\) hides \(\operatorname{poly}(\log\log n,\log k,\log(1/\varepsilon)\).) This was improved by Feldman and Langeberg [161] to \(O(k\log n/\varepsilon^{2})\). We introduce high-level ideas of [160] later. Given the coreset, it remains to give a good parameterized approximation algorithm for the problem for a much smaller (albeit weighted) point set \(|P|=O(\operatorname{poly}(\log n,k))\). Note that \(|F|\) can be still as large as \(n\), so naively choosing \(k\) centers from \(F\) will take \(n^{k}\) time and exhaustively partitioning \(P\) into \(k\) sets will take \(k^{|P|}=n^{\operatorname{poly}(k)}\) time. (Indeed, exactly solving this small case will give an EPAS, which will contradict the Gap-ETH.)