Consistent k-Median: Simpler, Better and Robust

In this paper we introduce and study the online consistent k-clustering with outliers problem, generalizing the non-outlier version of the problem studied by Lattanzi and Vassilvitskii (2017). We show that a simple local-search based online algorithm can give a bicriteria constant approximation for the problem with O(k² log²(nD)) swaps of medians (recourse) in total, where D is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of (Lattanzi and Vassilvitskii, 2017).