# Connected k-Median with Disjoint and Non-disjoint Clusters

arXiv: https://arxiv.org/abs/2507.02774 · HTML: https://mlsanity.com/paper/2507.02774/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy](https://mlsanity.com/paper/2608.14215/) (2026)

## Abstract (arXiv)

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 O(k2 log n)-approximation algorithm for the problem. We complement it with an Omega(n1-ε)-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.