We study the connected $k$-median clustering problem, which augments the classic $k$-median objective with connectivity constraints. The input consists of a metric space $(V,d)$ and a connected graph $G$ on the same vertex set $V$ (with $|V|=n$). The goal is to select at most $k$ centers $C$ and assign vertices to them so that the $k$-median cost $\sum_{v\in V} d(v,C)$ is minimized, while each cluster induces a connected subgraph of $G$. Because the metric space and the connectivity graph are independent, the problem is considerably harder than standard clustering.
Prior work by Eube et al. (2025) showed that even the assignment‑only version is $\Omega(\log n)$‑hard to approximate and provided algorithms whose guarantees grow polynomially with $k$. We introduce a configuration‑LP framework that combines covering‑LP techniques with a rooted minimum‑density oracle.
- Assignment version: Using the configuration LP we obtain an $O(\log^2 n)$ approximation.
- General version: We develop a bicriteria scheme that opens $O(k\log n)$ centers while achieving an $O(\log^2 n)$ approximation on the cost.
This framework demonstrates that configuration LPs, covering LPs, and rooted density oracles can be effectively combined to handle clustering objectives under graph‑theoretic constraints.
Blogger's Review: The paper offers a fresh LP‑based perspective, especially the techniques for enforcing connectivity, which are valuable for future research in constrained clustering.