[Proof Sketch]
The known offline coreset constructions start with a bicriterion solution of \(O(k)\)  points.
We modify the algorithm of [1]} to output \(O(k \log n)\)  centers; this is trivial since the final step of the algorithm of [1]} is to take the \(O(k \log n)\)  centers stored in memory and reduce them to exactly \(k\)  centers to provide a solution.
Our first modification to the original algorithm is thus to simply remove this final step, but we must also keep a datastructure storing \(\log (1/\epsilon )\)  intermediate states of these \(O(k \log n)\)  centers.
See Section  for a precise description of our modification and the sampling method, applied to the construction of [3]} as an example (but equally applicable to [4]}, [5]}, [6]}).
As the high-level idea, since the bicriterion given to the offline construction consists of \(O(k \log n)\)  centers instead of exactly \(k\) , the number of additional points taken in the coreset increases by a factor of \(O(\log n)\) .
