Connected k-Median with Disjoint and Non-disjoint Clusters
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911037147578368 |
|---|---|
| author | Eube, Jan Luo, Kelin Reineccius, Dorian Röglin, Heiko Schmidt, Melanie |
| author_facet | Eube, Jan Luo, Kelin Reineccius, Dorian Röglin, Heiko Schmidt, Melanie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02774 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connected k-Median with Disjoint and Non-disjoint Clusters Eube, Jan Luo, Kelin Reineccius, Dorian Röglin, Heiko Schmidt, Melanie Data Structures and Algorithms 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. |
| title | Connected k-Median with Disjoint and Non-disjoint Clusters |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.02774 |