It was proven in [1]} that for problems such as \(k\) -median such weak coresets have dimension \(O(k/\varepsilon )\) , i.e., independent of \(d\) . Unlike [1]}, we suggest here a very simple way to extract the approximated solution from the coreset: compute the weighted coreset \((S,u)\)  (of size independent of \(d\) ) as defined in Algorithm , and then use any given algorithm to compute a \((1+\varepsilon )\)  approximation set \(C\)  of \(k\)  centers on the coreset (or any other trusted heuristic that we hope computes such a set \(C\) ). Since \(C\)  is not necessarily spanned by few points in \(S\) , it may not be a good approximation for the original set \(P\)  and we should not return it. However,the proof in [3]} is constructive and shows a near-linear time algorithm that using such an approximated solution set \(C\) , we can compute another \((1+O(\varepsilon ))\) -approximation \(C^{\prime }\)  that has the additional property that \(C^{\prime }\)  is spanned by \(O(k/\varepsilon )\)  points in \(S\) . Hence, \(C^{\prime }\)  is both a near-optimal solution to \(S\)  and in \(Q(S)\) , so it must be a \((1+\varepsilon )\) -approximation for the optimal solution of \(P\) .
