A Configuration-LP Framework for Connected $k$-Median Clustering
Data Structures and Algorithms
Summary
The authors study a clustering problem where each group of points must be connected in a given graph, and clusters can overlap by sharing points. They look at a version that is harder than usual because the distance and graph connections come from different sources. Building on previous work that showed this problem is tough to approximate, the authors create a new mathematical approach combining different techniques to group points efficiently. Their methods achieve good approximate solutions, especially when allowing more clusters than originally limited. This work offers new ways to handle connectivity rules in clustering problems using advanced optimization tools.
Authors
Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
Abstract
We study the \emph{connected $k$-median} clustering problem, a clustering problem that augments the classical $k$-median objective with connectivity constraints. We focus on the \emph{overlapping} variant of the problem, where clusters are allowed to share vertices. In addition to a metric space $(V,d)$, the input contains a connected graph $G$ on the same vertex set $V$ of size $n$. The goal is to select at most $k$ centers $C$ and assign vertices to them so as to minimize the $k$-median cost (i.e., $\sum_{v\in V} d(v,C)$), subject to the constraint that each cluster induces a connected subgraph of $G$. Since the metric space and the connectivity graph are independent, the problem is significantly more challenging than standard clustering. Eube et al.~\cite{eube2025esa} showed that even the assignment version is $Ω(\log n)$-hard to approximate and gave approximation algorithms with guarantees depending polynomially on $k$. We develop a configuration-LP-based framework that combines covering LP techniques with a rooted minimum-density oracle. For the assignment version, we obtain an $O(\log^2 n)$-approximation. For the general version, we develop a bicriteria framework that opens $O(k\log n)$ centers while achieving an $O(\log^2 n)$-approximation in cost. %Our results provide a different LP-based approach for handling connectivity constraints in clustering problems and demonstrate that configuration LPs, covering LPs, and rooted density oracles can be combined effectively to obtain approximation guarantees for clustering objectives under graph-theoretic constraints.