Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs

2023/10/03 by Lukas Drexler, Jan Höckendorff, Drexler, Lukas +5
Business, Management and Accounting · Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management

paper · pdf · doi:10.48550/arxiv.2310.02130

openalex publication_date 2023/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the following natural problem that generalizes min-sum-radii clustering: Given is k∈ℕ as well as some metric space (V,d) where V=F∪ C for facilities F and clients C. The goal is to find a clustering given by k facility-radius pairs (f₁,r₁),…,(f_k,r_k)∈ F×ℝ_{≥ 0} such that C⊆ B(f₁,r₁)∪…∪ B(f_k,r_k) and ∑_i=1,…,k g(r_i) is minimized for some increasing function g:ℝ_{≥ 0}→ℝ_{≥ 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.

Related

• Dynamic clustering to minimize the sum of radii
• Improved fixed-parameter bounds for Min-Sum-Radii and Diameters k-clustering and their fair variants
• Clustering in Varying Metrics
• Clustering to Minimize Cluster-Aware Norm Objectives
• Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering