Online Clustering with Stochastic Arrivals

We study online $k$-clustering under strict consistency constraints: points are irrevocably assigned to a cluster and there is zero recourse (centers cannot be moved or closed). While achieving bounded costs under these constraints is impossible in the worst case without significantly relaxing the problem, we introduce the first framework for *online clustering with stochastic arrivals* to circumvent these adversarial lower bounds. By making mild stochastic modeling assumptions, we provide novel algorithms for the $k$-center and $k$-median objectives that achieve $O(1)$-approximations. Our algorithms strictly adhere to zero recourse and irrevocable assignments by utilizing a parsimonious amount of resource augmentation, opening at most $(1+ϵ)k$ centers in expectation for any constant $ϵ>0$. Moreover, our algorithms have two additional properties that are extremely important in practice. First, they need only minimal information about the distribution: the expected cost of the optimal solution. Second, our algorithms are robust to model mis-specification — the performance of our algorithms smoothly degrades as our estimate of this expectation differs from the true expectation. Put together, these two properties mean that we need only to assume a weak estimate of one particular statistic about the distribution, rather than assuming full knowledge. We validate our theoretical results with experiments demonstrating the superior performance of our algorithms when distributional information is available.