Connected clustering denotes a family of constrained clustering problems in which we are given a distance metric and an undirected connectivity graph G that can be completely unrelated to the metric. The aim is to partition the n vertices into a given number k of clusters such that every cluster forms a connected subgraph of G and a given clustering objective gets minimized. The constraint that the clusters are connected has applications in many different fields, like for example community detection and geodesy.<\/p>\n
So far, k-center and k-median have been studied in this setting. It has been shown that connected k-median is $\\Omega(n^{1- \\epsilon})$-hard to approximate which also carries over to the connected k-means problem, while for connected k-center it remained an open question whether one can find a constant approximation in polynomial time. We answer this question by providing an $\\Omega(\\log^*(k))$-hardness result for the problem. Given these hardness results, we study the problems on graphs with bounded treewidth. We provide exact algorithms that run in polynomial time if the treewidth w is a constant. Furthermore, we obtain constant approximation algorithms that run in FPT time with respect to the parameter max(w,k).<\/p>\n
Additionally, we consider the min-sum-radii (MSR) and min-sum-diameter (MSD) objective. We prove that on general graphs connected MSR can be approximated with an approximation factor of $(3+\\epsilon)$ and connected MSD with an approximation factor of $(4+\\epsilon)$. The latter also directly improves the best known approximation guarantee for unconstrained MSD from $(6+\\epsilon)$ to $(4+\\epsilon)$.<\/p>\n","protected":false},"excerpt":{"rendered":"
Connected clustering denotes a family of constrained clustering problems in which we are given a distance metric and an undirected connectivity graph G that can be completely unrelated to the metric. The aim is to partition the n vertices into a given number k of clusters such that every cluster forms a connected subgraph of G and a given clustering objective gets minimized. The constraint that the clusters are connected […]<\/p>\n","protected":false},"author":14,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[30],"class_list":["post-32191","publication","type-publication","status-publish","hentry","publication-type-article"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32191","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/14"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32191\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32191"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}