我们研究 连通 $k$-median 聚类问题，它在经典 $k$-median 目标上加入了连通性约束。输入包括度量空间 $(V,d)$ 和同一顶点集 $V$ 上的连通图 $G$（$|V|=n$）。目标是选取至多 $k$ 个中心 $C$ 并将顶点分配给中心，使 $k$-median 成本 $\sum_{v\in V} d(v,C)$ 最小，同时每个簇在 $G$ 中诱导的子图必须连通。由于度量空间与连通图相互独立，问题比标准聚类更具挑战。
先前工作 Eube 等人（2025）证明即使是仅考虑分配的版本也难以在 $\Omega(\log n)$ 以内近似，并给出了近似比随 $k$ 多项式增长的算法。我们提出了一套基于配置线性规划的框架，结合覆盖 LP 技术和根式最小密度 oracle。
- 分配版本：通过配置 LP 我们得到 $O(\log^2 n)$ 的近似算法。
- 一般版本：构建双准则方案，打开 $O(k\log n)$ 个中心并实现 $O(\log^2 n)$ 的成本近似。
该框架展示了配置 LP、覆盖 LP 与根式密度 oracle 的有效组合，可在图论约束下处理聚类目标。
博主点评：该工作提供了新的 LP 思路，尤其在处理连通约束时的技巧值得关注，对后续研究具有启发意义。