标题： 连接的k-中位数问题具有不相交和相交的聚类 显示英文标题

标题： Connected k-Median with Disjoint and Non-disjoint Clusters

摘要： 连接的$k$中位数问题是一个结合基于距离的$k$聚类与连通性信息的约束聚类问题。 该问题允许输入一个度量空间和一个与度量空间完全无关的无权无向连通图。 目标是计算$k$个中心及其对应的聚类，使得每个聚类形成$G$的连通子图，并且使$k$中位数成本最小化。 该问题在地质测量（特别是区域划分）、社交网络分析（尤其是社区检测）或生物信息学等不同领域有应用。 我们研究了一个具有重叠聚类的版本，其中点可以属于多个聚类，这对于社区检测的用例来说是自然的。 这个问题变体是$\Omega(\log n)$难以近似的，我们的主要结果是该问题的一个$\mathcal{O}(k^2 \log n)$近似算法。 我们补充了一个$\Omega(n^{1-\epsilon})$-hardness 结果，针对不与一般连通图重叠的不相交聚类情况，以及在连通图是树的情况下在此设置中的精确算法。 显示英文摘要

摘要： The connected $k$-median problem is a constrained clustering problem that combines distance-based $k$-clustering with connectivity information. The problem allows to input a metric space and an unweighted undirected connectivity graph that is completely unrelated to the metric space. The goal is to compute $k$ centers and corresponding clusters such that each cluster forms a connected subgraph of $G$, and such that the $k$-median cost is minimized. The problem has applications in very different fields like geodesy (particularly districting), social network analysis (especially community detection), or bioinformatics. We study a version with overlapping clusters where points can be part of multiple clusters which is natural for the use case of community detection. This problem variant is $\Omega(\log n)$-hard to approximate, and our main result is an $\mathcal{O}(k^2 \log n)$-approximation algorithm for the problem. We complement it with an $\Omega(n^{1-\epsilon})$-hardness result for the case of disjoint clusters without overlap with general connectivity graphs, as well as an exact algorithm in this setting if the connectivity graph is a tree.