{"ID":2898841,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.02774","arxiv_id":"2507.02774","title":"Connected k-Median with Disjoint and Non-disjoint Clusters","abstract":"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 $Ω(\\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 $Ω(n^{1-ε})$-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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2507.02774","url_pdf":"https://arxiv.org/pdf/2507.02774v1","authors":"[\"Jan Eube\",\"Kelin Luo\",\"Dorian Reineccius\",\"Heiko Röglin\",\"Melanie Schmidt\"]","published":"2025-07-03T16:35:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}