## 1 Introduction
### Clustering  
For a given similarity measure, clustering is the problem of partitioning an input set of \(n\) objects into subsets, such that objects in the same group are more similar to each other than to objects in the other sets. As mentioned in [1], clustering problems arise in many different applications, including data mining and knowledge discovery [2], data compression and vector quantization [3], and pattern recognition and classification [4]. However, for most of its variants, it is an NP-Hard problem when the number \(k\) of clusters is part of the input, as elaborated and proved in [5, 6]. In fact, the exponential dependency in \(k\) is unavoidable even for approximating the (regular) Euclidean \(k\)-means for clustering \(n\) points in the plane [7, 8].  
Hence, constant or near-constant (logarithmic in \(n\) or \(k\)) multiplicative factor approximations to the desired cost function were suggested over the years, whose running time is polynomial in both \(n\) and \(k\). Arguably, the most common version in both academy and industry is the \(k\)-means cost function, where the input is a set of \(n\) points in a metric space, and the goal is to compute the set of \(k\) centers (points) that minimizes the sum of squared distances over each input point to its closest center.  
The \(k\)-means++ method that was suggested independently by [9, 10] is an extremely common and simple solution with probable approximation bounds. It provides an \(\alpha\in O(\log k)\) multiplicative approximation in time \(O(dnk)\), e.g., for the Euclidean \(d\)-dimensional space. It was also shown in [10] that the approximation factor is \(\alpha=O(1)\), if the input data is well separated in some formal sense.  
Recently, Ref. [11] provided an \(\alpha\in O(1)\) approximation for points in the \(d\)-dimensional Euclidean space via exactly \(k\) centers in time complexity of \(O(dnk^{2}\log\log k)\).  
The \(k\)-means++ algorithm is based on the intuition that the centroids should be well spread out. Hence, it samples \(k\) centers iteratively, via a distribution that is called \(D^{2}\)-sampling and is proportional to the distance of each input point to the centers that were already chosen. The first center is chosen uniformly at random from the input.  
The \(k\)-means++ algorithm supports any distance to the power of \(z\geq 1\) as explained in [9]. Deterministic and other versions for the sum of (nonsquared) distances were suggested in [12; 13; 14].  
A more general approximations, called _bicriteria_ or \((\alpha,\beta)\) approximations, guarantee multiplicative factor \(\alpha\)-approximation but the number of used center (for approximating the optimal \(k\) centers) is \(\beta k\) for some \(\beta>1\). The factors \(\alpha\) and \(\beta\) might be depended on \(k\) and \(n\), and different methods give different dependencies and running times. For example, Ref. [15] showed that sampling \(O(k\log k)\) different randomized centers yields an \(O(1)\)-approximation and leverage it to support streaming data. Similarly, it was proved in [16] that \(D^{2}\)-sampling \(O(k)\) centers yields an \(O(1)\) approximation.  
The analysis of [17] explores the value of \(\alpha\) as a function of \(\beta\).  
A coreset for the \(k\)-median/mean problem is a small weighted set (usually subset) of the input points that approximates the sum of distances or sum of squared distances from the original (big) set \(P\) to _every_ given set of \(k\) centers, usually up to \((1+\varepsilon)\) multiplicative factor. In particular, we may compute an \(\alpha\)-approximation on the coreset to obtain \(\alpha(1+\varepsilon)\)-approximation for the original data.  
For the special case of \(k\)-means in the Euclidean space we can replace \(d\) by \(O(k/\varepsilon^{2})\), including for coresets constructions, as explained in [18]. Deterministic coresets for \(k\)-means of size independent of \(d\) were suggested in [19].