论文标题
在电容聚类的固定参数障碍上
On the Fixed-Parameter Tractability of Capacitated Clustering
论文作者
论文摘要
我们研究了经典电容的K-Median和K-均值问题的复杂性，该问题由中心数量k进行了参数。众所周知，这些问题是困难的，因为对于高维欧几里得空间而言，最著名的近似值和一般度量空间为$θ（\ log k）$，并且是否存在恒定因子，这仍然是一个主要的开放问题。我们表明，存在电容的K-Median的$（3+ε）$ - 近似算法，在一般度量空间中，运行时间为$ f（ε）n^{o（1）O（a）n^{o（1）} $中的电容k-均值问题的$（9+ε）$ - 近似算法。对于任意维度的欧几里得输入，我们给出了$（1+ε）$ - 近似算法，对于这两个问题，都具有相似的运行时间。这是Adamczyk等人的$（7+ε）$ - 近似的显着改善。对于一般度量空间中的K-Median和Xu等人的$（69+ε）$ - 近似。对于欧几里得K-均值。
We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best known approximation bound for high dimensional Euclidean space and general metric space is $Θ(\log k)$ and it remains a major open problem whether a constant factor exists. We show that there exists a $(3+ε)$-approximation algorithm for the capacitated k-median and a $(9+ε)$-approximation algorithm for the capacitated k-means problem in general metric spaces whose running times are $f(ε,k) n^{O(1)}$. For Euclidean inputs of arbitrary dimension, we give a $(1+ε)$-approximation algorithm for both problems with a similar running time. This is a significant improvement over the $(7+ε)$-approximation of Adamczyk et al. for k-median in general metric spaces and the $(69+ε)$-approximation of Xu et al. for Euclidean k-means.
