Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set $X$ of $n$ points and two integers $k$ and $m$, the clustering with outliers aims to exclude $m$ points from $X$ and partition the remaining points into $k$ clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in $k$ and $m$, that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for $k$-Median and $k$-Means with outliers in general metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.
翻译:在计算机科学中,外围线是最重要的问题之一。鉴于设定的美元值为10美元,两整数为1美元和1美元,外线线群集的目的是从X美元中排除1美元点,并将其余点分成1美元组,以最大限度地减少某种成本功能。在本文中,我们给出了解决外围线群集的一般方法,从而产生了固定参数可移动的1美元和1美元算法,几乎与非直接线对口方的近似比率相匹配。作为必然结果,我们获得了具有美元-美元和美元-美元最佳近似比率的远端近似算法,并在一般指标中将其余点分为1美元组。我们还展示了我们对于问题的其他变式方法的更多应用,这些变式对集群施加了额外的限制,例如公平性或甲状体约束。