# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Clustering
#### 4.3.2 Euclidean Space  
For Euclidean spaces, we assume that \(X=F=\mathbb{R}^{d}\) for some \(d\in\mathbb{N}\), endowed with the standard \(\ell_{2}\) metric. Let \(n=|P|\) in this subsection. Now we have \(k\) and \(d\) as natural structural parameters of clustering tasks. Many previous approximation algorithms in Euclidean \(k\)-Median and Euclidean \(k\)-Means in Euclidean spaces, without explicit mention to parameterized complexity, are parameterized approximation algorithms parameterized by \(k\) or \(d\) (or both). The highlight of this subsection is that for both Euclidean \(k\)-Median and Euclidean \(k\)-Means, an EPAS exists with only one of \(k\) and \(d\) as a parameter. Without any parameterization, both Euclidean \(k\)-Median and \(k\)-Means are known to be APX-hard [164; 165]. We introduce these results in the chronological order, highlighting important ideas. Euclidean \(k\)-Median with parameter \(d\)The first PTAS for Euclidean \(k\)-Median in Euclidean spaces with fixed \(d\) appears in Arora et al. [166]. The techniques extend Arora's previous PTAS for the Euclidean Traveling Salesman problem in Euclidean spaces [167], first proving that there exists a near-optimal solution that interacts with a quadtree (a geometric division of \(\mathbb{R}^{d}\) into a hierarchy of square regions) in a restricted sense, and finally finding such a tour using dynamic programming. The running time is \(n^{O(1/\varepsilon)}\) for \(d=2\) and \(n^{(\log n/\varepsilon)^{d-2}}\) for \(d>2\). Kolliopoulous and Rao [168] improved the running time to \(2^{O((\log(1/\varepsilon)/\varepsilon)^{d-1})}n\log^{d+6}n\), which is an EPAS with parameter \(d\). Euclidean \(k\)-Median and Euclidean \(k\)-Means with parameter \(k\). An EPAS for Euclidean \(k\)-Means even with parameters both \(k\) and \(d\) took longer to be discovered, and first appeared when Matousek [169] gave an approximation scheme that runs in time \(O(n\varepsilon^{2k^{2}d}\log^{k}n)\). After this, several improvements on the running time followed Badoiu et al. [170], De La Vega et al. [171], Har-Peled and Mazumdar [172]. Kumar et al. [173; 174] gave approximation schemes for both \(k\)-Median and \(k\)-Means, running in time \(2^{(k/\varepsilon)^{O(1)}}dn\). This shows that an EPAS can be obtained by using only \(k\) as a parameter. Using this result and and improved coresets, more improvements followed [160; 161; 175]. The current best runtime to get \((1+\varepsilon)\)-approximation is \(O(ndk+d\cdot\operatorname{poly}(k/\varepsilon)+2^{\tilde{O}(k/\varepsilon)})\) for \(k\)-Means[175], and \(O(ndk+2^{\operatorname{poly}(1/\varepsilon k)})\) time for \(k\)-Median[161]. A crucial property of the Euclidean space that allows an EPAS with parameter \(k\) (which is ruled out for general metrics by Theorem 4.2) is the sampling property, which says that for any set \(Q\subseteq\mathbb{R}^{d}\) as one cluster, there is an algorithm that is given only \(g(1/\varepsilon)\) samples from \(Q\) and outputs \(h(1/\varepsilon)\) candidate centers such that one of them is \(\varepsilon\)-close to the optimal center for the entire cluster \(Q\) for some functions \(g,h\). (For example, for \(k\)-Means, the mean of \(O(1/\varepsilon)\) random samples \(\varepsilon\)-approximates the actual mean with constant probability.) This idea leads to an \((1+\varepsilon)\)-approximation algorithm running in time \(|P|^{f(\varepsilon,k)}\). Together even with a general coreset construction of size \(\operatorname{poly}(k,\log n,1/\varepsilon)\), one already gets an EPAS with parameter \(k\). Better coresets construction are also given in Euclidean spaces. Recent developments [176; 177; 178] construct core-sets of size \(\operatorname{poly}(k,1/\varepsilon)\) (no dependence on \(n\) or \(d\)), which is further extended to the shortest-path metric of an excluded-minor graph [179]. Euclidean \(k\)-Means with parameter \(d\). Cohen-Addad et al. [180] and Friggstad et al. [181] recently gave approximation schemes running in time \(n^{f(d,\varepsilon)}\) using local search techniques.