Fully-Dynamic Coresets
share
With input sizes becoming massive, coresets—small yet representative summary of the input—are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1 ±ε] 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 ε-coreset algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1 -λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) · t(s(n, ε/log n, λ/n), ε/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. As a consequence, we get fully-dynamic ε-coreset algorithms for k-median and k-means with worst-case update time O(ε^-2k^2log^5 n log^3 k) and coreset size O(ε^-2klog n log^2 k) ignoring loglog n and log(1/ε) factors and assuming that ε, λ = Ω(1/poly(n)) (very weak assumptions made to make bounds easy to parse). These are the first fully-dynamic algorithms for k-median and k-means with worst-case update times O(poly(k, log n, ε^-1)). The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. via randomized O(1)-coresets in O(n) space.
READ FULL TEXT