论文标题
连接的K-Center和K直径集群
Connected k-Center and k-Diameter Clustering
论文作者
论文摘要
在Geodesy的应用程序中，我们引入了一个新颖的聚类问题，该问题是$ K $中心（或K直径）问题，并具有侧面约束。对于侧面约束，我们在输入点上给了我们一个无方向性的连接图$ g $，现在只有在每个群集诱导$ g $的连接子图的情况下，仅是可行的。我们称之为由此产生的问题，即连接的$ k $中心问题和连接的$ k $直径问题。 我们证明了这些问题的复杂性和近似性的几个结果。我们的主要结果是$ o（\ log^2 {k}）$ - 连接的$ k $ - 中心和连接的$ k $ - 直径问题的近似算法。对于具有持续加倍维度的欧几里得指标和指标，该算法的近似因素提高到$ O（1）$。我们还考虑了连接图是线或树的特殊情况。对于这条线，我们给出了最佳的多项式时间算法，并且对于连接图是树，我们要么给出最佳的多项式时间算法，要么为我们所有模型的所有变体提供了$ 2 $ - APPROXIMATION算法。我们通过几个下限来补充上限。
Motivated by an application from geodesy, we introduce a novel clustering problem which is a $k$-center (or k-diameter) problem with a side constraint. For the side constraint, we are given an undirected connectivity graph $G$ on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in $G$. We call the resulting problems the connected $k$-center problem and the connected $k$-diameter problem. We prove several results on the complexity and approximability of these problems. Our main result is an $O(\log^2{k})$-approximation algorithm for the connected $k$-center and the connected $k$-diameter problem. For Euclidean metrics and metrics with constant doubling dimension, the approximation factor of this algorithm improves to $O(1)$. We also consider the special cases that the connectivity graph is a line or a tree. For the line we give optimal polynomial-time algorithms and for the case that the connectivity graph is a tree, we either give an optimal polynomial-time algorithm or a $2$-approximation algorithm for all variants of our model. We complement our upper bounds by several lower bounds.
