Fully-Dynamic Coresets

With input sizes becoming massive, coresets -- small yet representative summary of the input -- are relevant more than ever. A weighted set Cw that is a subset of the input is an varepsilon-coreset if the cost of any feasible solution S with respect to Cw is within [1 ± varepsilon] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static varepsilon-coreset algorithm that runs in time t(n, varepsilon, λ) and computes a coreset of size s(n, varepsilon, λ), where n is the number of input points and 1 -λ is the success probability, we give a fully-dynamic algorithm that computes an varepsilon-coreset with worst-case update time O((log n) · t(s(n, varepsilon/log n, λ/n), varepsilon/log n, λ/n) ) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique that applies to insertion-only setting. Although our space usage is O(n), we work in the presence of an adaptive adversary, and we show that Omega(n) space is required when adversary is adaptive. As a consequence, we get fully-dynamic varepsilon-coreset algorithms for k-median and k-means with worst-case update time O(varepsilon-2k2log5 n log3 k) and coreset size O(varepsilon-2klog n log2 k) ignoring log log n and log(1/varepsilon) factors and assuming that varepsilon, λ = Omega(1/poly(n)). These are the first fully-dynamic algorithms for k-median and k-means with worst-case update times O(poly(k, log n, varepsilon-1)). We also give conditional lower bound on update/query time for any fully-dynamic (4 - δ)-approximation algorithm for k-means.