论文标题
一致的$ k $ -Median：更简单，更好，健壮
Consistent $k$-Median: Simpler, Better and Robust
论文作者
论文摘要
在本文中，我们介绍并研究了与异常值问题的在线一致$ k $ clustering，从而概括了[lattanzi-vassilvitskii，icml17]中研究的非外观版本。 我们表明，一种简单的基于本地搜索的在线算法可以通过$ o（k^2 \ log^2（nd））$互换中位数（追索权）的$ O（k^2 \ log^2（nd））给出一个平均近似值，其中$ d $是指标的直径。与[Lattanzi-vassilvitskii，icml17]相比，当限制在没有异常值的问题的情况下，我们的算法更简单，确定性并提供更好的近似值和追索权。
In this paper we introduce and study the online consistent $k$-clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvitskii, ICML17]. We show that a simple local-search based online algorithm can give a bicriteria constant approximation for the problem with $O(k^2 \log^2 (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-Vassilvitskii, ICML17].
