{"id":32815,"date":"2026-01-21T17:02:42","date_gmt":"2026-01-21T17:02:42","guid":{"rendered":"https:\/\/lamarr-institute.org\/publication\/clustering-graphs-of-bounded-treewidth-to-minimize-the-sum-of-radius-dependent-costs\/"},"modified":"2026-09-17T11:26:26","modified_gmt":"2026-09-17T11:26:26","slug":"clustering-graphs-of-bounded-treewidth-to-minimize-the-sum-of-radius-dependent-costs","status":"publish","type":"publication","link":"https:\/\/lamarr-institute.org\/de\/publication\/clustering-graphs-of-bounded-treewidth-to-minimize-the-sum-of-radius-dependent-costs\/","title":{"rendered":"Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs"},"content":{"rendered":"<p>We consider the following natural problem that generalizes min-sum-radii clustering: Given is $k \\in \\mathbb{N}$ as well as some metric space $(V, d)$ where $V = F \\cup C$ for facilities $F$ and clients $C$. The goal is to find a clustering given by $k$ facility-radius pairs $(f_1, r_1), \\dots, (f_k, r_k) \\in F \\times \\mathbb{R}{\\geq 0}$ such that $C \\subseteq B(f_1, r_1) \\cup \\cdots \\cup B(f_k, r_k)$ and $\\sum{i=1, \\dots, k} g(r_i)$ is minimized for some increasing function $g : \\mathbb{R}{\\geq 0} \\to \\mathbb{R}{\\geq 0}$. Here, $B(x, r)$ is the radius-$r$ ball centered at $x$. For the case that $(V, d)$ is the shortest-path metric of some edge-weighted graph of bounded treewidth, we present a dynamic program that is tailored to this class of problems and achieves a polynomial running time, establishing that the problem is in XP with parameter treewidth.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We consider the following natural problem that generalizes min-sum-radii clustering: Given is $k \\in \\mathbb{N}$ as well as some metric space $(V, d)$ where $V = F \\cup C$ for facilities $F$ and clients $C$. The goal is to find a clustering given by $k$ facility-radius pairs $(f_1, r_1), \\dots, (f_k, r_k) \\in F \\times \\mathbb{R}{\\geq 0}$ such that $C \\subseteq B(f_1, r_1) \\cup \\cdots \\cup B(f_k, r_k)$ and $\\sum{i=1, [&hellip;]<\/p>\n","protected":false},"author":14,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[30],"class_list":["post-32815","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\/32815","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\/32815\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32815"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}