论文标题
Min-sum聚类（带异常值）
Min-Sum Clustering (with Outliers)
论文作者
论文摘要
我们给出一个恒定因子多项式时间伪及其，用于带有或没有异常值的Min-sum聚类。该算法被允许排除任意少量恒定分数。例如，我们显示如何计算一个解决方案，该解决方案将98 \％的输入数据点和付费不超过恒定因子乘以最佳解决方案的最佳解决方案，该解决方案将99 \％的输入数据点簇。 More generally, we give the following bicriteria approximation: For any $\eps > 0$, for any instance with $n$ input points and for any positive integer $n'\le n$, we compute in polynomial time a clustering of at least $(1-\eps) n'$ points of cost at most a constant factor greater than the optimal cost of clustering $n'$ points.近似保证随$ \ frac {1} {\ eps} $增长。我们的结果适用于具有平方的欧几里得距离以及指标空间中的点的实际空间中点的实例，其中簇数的数量，以及如果相关的尺寸是任意的（输入的一部分，而不是绝对常数）。
We give a constant factor polynomial time pseudo-approximation algorithm for min-sum clustering with or without outliers. The algorithm is allowed to exclude an arbitrarily small constant fraction of the points. For instance, we show how to compute a solution that clusters 98\% of the input data points and pays no more than a constant factor times the optimal solution that clusters 99\% of the input data points. More generally, we give the following bicriteria approximation: For any $\eps > 0$, for any instance with $n$ input points and for any positive integer $n'\le n$, we compute in polynomial time a clustering of at least $(1-\eps) n'$ points of cost at most a constant factor greater than the optimal cost of clustering $n'$ points. The approximation guarantee grows with $\frac{1}{\eps}$. Our results apply to instances of points in real space endowed with squared Euclidean distance, as well as to points in a metric space, where the number of clusters, and also the dimension if relevant, is arbitrary (part of the input, not an absolute constant).
