Our method can be applied to the coreset constructions of [1]}, [2]}, [3]}, [4]} with a multiplicative overhead of \(O(\log n)\) .
Our second theorem is a more generally applicable technique; it applies to all constructions that first compute a bicriterion solution and then sample points according to the bicriterion solution. The constructions of [1]}, [2]}, [3]}, [4]} follow this outline, and we are unaware of any constructions which do not. The theorem yields immediate corollaries as well as reducing certain streaming coreset problems to that of constructing an offline coreset.
