Average Sensitivity of Euclidean k-Clustering

Given a set of n points in R d , the goal of Euclidean ( k, (cid:96) ) -clustering is to find k centers that minimize the sum of the (cid:96) -th powers of the Euclidean distance of each point to the closest center. In practical situations, the clustering result must be stable against points missing in the input data so that we can make trustworthy and consistent decisions. To address this issue, we consider the average sensitivity of Euclidean ( k, (cid:96) ) -clustering, which measures the stability of the output in total variation distance against deleting a random point from the input data. We first show that a popular algorithm k - MEANS ++ and its variant called D (cid:96) - SAMPLING have low average sensitivity. Next, we show that any approximation algorithm for Euclidean ( k, (cid:96) ) -clustering can be transformed to an algorithm with low average sensitivity while almost preserving the approximation guarantee. As byproducts of our results, we provide several algorithms for consistent ( k, (cid:96) ) -clustering and dynamic ( k, (cid:96) ) -clustering in the random-order model, where the input points are randomly permuted and given in an online manner. The goal of the consistent setting is to maintain a good solution while minimizing the number of changes to the solution during the process, and that of the dynamic setting is to maintain a good solution while minimizing the (amortized) update time.