For the non-Euclidean case or non-squared distances it seems that it is impossible to obtain coreset of size independent of \(d\) . However, coreset as defined above (sometimes called strong coreset) approximates every query in the set of queries, while the main application and motivation for constructing coreset is to compute the optimal query or its approximation. A weak coreset is a small set that can be used to give such an approximation. The exact definition of weak coreset also changes from paper to paper. In particular, a weak coreset for \(k\) -means was suggested in [1]}. However, to extract the approximated solution from the coreset we must run an exhaustive search and cannot use existing algorithms or heuristics as in the case of strong coreset.
