Source-linked AI summary
A Configuration-LP Framework for Connected $k$-Median Clustering
Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
TL;DR
Connected k-median combines metric clustering with connectivity constraints from an independent graph, making even assignment difficult. The paper uses connected rooted configurations in a configuration LP, combined with covering methods and rooted minimum-density oracles. It achieves O(log2 n) approximation for assignment and an (O(log n), O(log2 n)) bicriteria guarantee for the general version.
Problem
Connected k-median seeks low metric cost while requiring graph-connected clusters, with independent metric and connectivity structures making the problem harder than classical k-median.
Method
The framework uses configuration-LP variables for connected sets rooted at centers, combined with covering-LP techniques and rooted minimum-density oracles.
Results
The paper obtains an O(log2 n)-approximation for assignment and an (O(log n), O(log2 n)) bicriteria approximation for the general version.
Takeaways & Limitations
Configuration LPs provide a structured way to encode connectivity directly and support polylogarithmic guarantees when bicriteria center opening is allowed.
Takeaways & Limitations
The general version with exactly k centers remains an open question, and the configuration LP has exponentially many variables requiring approximate solution by column generation.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses overlapping connected k-median, where independent metric and graph structures require connected clusters, and develops a configuration-LP framework with covering and rooted-density techniques. It obtains polylogarithmic assignment guarantees and a bicriteria general-version guarantee that removes polynomial dependence on k from the cost factor.
- Problem: Independent metric and connectivity graphs make connected k-median substantially more challenging than classical k-median.The problem requires each cluster to induce a connected subgraph while minimizing metric assignment cost.
- Problem: The overlapping variant permits vertices to belong to multiple clusters, supporting applications such as community detection and articulation-point connectivity.This variant is theoretically important because the disjoint version has an Ω(n1−ε) lower bound even for k = 2.
- Prior work: Connectivity constraints yield an Ω(log n)-hard assignment problem, while prior algorithms achieve O(k log n) for assignment and O(k2 log n) for the general version.These guarantees expose the difficulty gap between classical and connected k-median.
- Framework: The configuration-LP framework indexes variables by connected sets rooted at centers, encoding connectivity directly rather than through cut constraints.It combines covering-LP techniques with rooted minimum-density oracles.
- Results: O(log2 n) approximation is achieved for assignment on general graphs, improving the prior assignment result when k = ω(log n).The rounding samples configurations independently with logarithmic oversampling, preserving connectivity through unions sharing a root.
- Results: At most O(k log n) centers and an O(log2 n) cost approximation are obtained for the general version through bicriteria rounding.This replaces the prior O(k2 log n) cost dependence with a polylogarithmic factor while allowing more centers.
2 Preliminaries and Problem Statement
The paper formalizes overlapping connected k-median, where clusters must be connected in a graph independent of the metric, and states assignment and bicriteria results.
- Problem Statement: Connected k-median minimizes metric assignment cost while requiring every cluster to induce a connected subgraph of the connectivity graph.The metric and graph are independent inputs.
- Problem Statement: Overlapping solutions allow vertices to belong to multiple clusters, with each cluster assignment contributing separately to the objective.
- Problem Statement: The assignment version fixes at most k centers, whereas the general version must choose both the centers and connected clusters.
- Results: O(log^2 n) is achieved for assignment connected k-median when k = ω(log n).The algorithm is polynomial-time and applies to general connectivity graphs.
- Results: (O(log n), O(log^2 n)) is achieved for the general version using a bicriteria solution.The first factor bounds the center count and the second bounds cost.
3 Assignment Version
For fixed centers, the paper models connected clusters with an exponential configuration covering LP, solves it through density-oracle pricing, and rounds the fractional solution.
- Configuration LP: The exponentially large covering LP is solved approximately using Plotkin–Shmoys–Tardos multiplicative updates and an approximate rooted minimum-density oracle.The oracle supplies approximately best columns for the covering formulation.
- Approximation: O(ρ log n) is the resulting approximation from a ρ-approximate density oracle, yielding O(log^2 n) when ρ = O(log n).
- Configuration LP: Each configuration is a connected vertex set T containing a fixed center c, represented by a variable y_T,c.The LP covers vertices using connected configurations rooted at their designated centers.
- Density Oracle: O(log n) is the approximation ratio of the polynomial-time rooted minimum-density oracle on general graphs.
- Rounding: Randomized rounding converts a polynomial-support feasible fractional solution into a feasible integral overlapping clustering with O(log n) cost inflation.Repeated independent runs produce the guarantee with high probability.
4 General Version
For the general version, a configuration LP includes a fractional center budget, is solved with density-oracle pricing, and is rounded into a bicriteria clustering.
- Configuration LP: The general configuration LP uses variables for connected sets rooted at every possible center and constrains total configuration mass by k.This provides a fractional relaxation of opening at most k centers.
- Fractional Solution: A ρ-approximate rooted minimum-density oracle enables polynomial-time computation of a polynomial-support fractional solution with cost O(ρ) times the LP optimum.The mixed packing/covering framework supplies the approximation and polynomial support.
- Theorem 2: O(log^2 n) cost approximation is obtained on general graphs, together with the O(k log n) center bound.The rounding adds an O(log n) factor to the fractional solution, and the density oracle has ρ = O(log n).
- Rounding: Sampling each supported configuration with probability min{1, λ ln n·ŷ_T,c} preserves connectedness because unions of sampled configurations sharing a root remain connected.
- Rounding: O(k log n) centers are opened with high probability, while all vertices are covered with high probability.The center bound follows from a Chernoff bound and coverage from a union bound.
5 Conclusion and Open Problems
The paper develops a configuration-LP framework for connected k-median and obtains logarithmic approximation guarantees for assignment and bicriteria general variants. It also identifies extensions to other connectivity-constrained clustering problems and open questions concerning exact-k solutions and stronger density oracles.
- The framework encodes connectivity directly through connected configurations rooted at centers, combining covering-LP techniques with rooted minimum-density oracles.
- O(log^2 n) approximation is obtained for the assignment version on general graphs.
- The general version receives an (O(log n), O(log^2 n)) bicriteria approximation.
- The framework may extend to related constrained clustering objectives by separating covering-LP computation from rooted density optimization.
A Proof of Lemma 3.1
A feasible overlapping connected-clustering solution induces a feasible configuration-LP solution with exactly the same cost. Therefore, the configuration LP is a relaxation whose optimum is at most the optimal clustering cost for the prescribed centers.
- Each cluster containing its center and inducing a connected subgraph is a valid center-rooted configuration.
- Assigning value 1 to each selected cluster configuration and 0 to all others preserves coverage of every non-center vertex.
- All constructed configuration variables are nonnegative, satisfying the LP nonnegativity constraints.
- The induced LP solution has exactly the cost of the original integral solution.
- Consequently, the configuration-LP optimum is at most OPT for the assignment variant with prescribed center set C.
B Proof of Lemma 3.2
A rooted budgeted Steiner-tree approximation is converted into a polynomial-time rooted minimum-density oracle. Geometric budget guessing and density selection yield an O(log n)-approximation.
- The rooted budgeted node-weighted Steiner-tree oracle allows a factor-2 budget violation and an O(log n)-dependent profit approximation.
- Geometric budgets include one value B⋆ satisfying w(T*) ≤ B⋆ ≤ 2w(T*).
- The selected tree has weight at most 4w(T*) and profit at least α(T*)/O(log n).
- Choosing the minimum-density tree among tried budgets produces an O(log n)-approximate density oracle in polynomial time.
C Proof of Theorem 4
The proof transforms an approximate pricing oracle into a point-finding oracle over fixed-cost simplices, applies fractional-covering machinery, and binary-searches the unknown optimum. Rescaling the final near-cover produces a feasible solution with controlled cost and polynomial running time.
- The covering LP has exponentially many columns, so the proof uses approximate oracle access instead of solving it directly.
- Part 1: from pricing to index-finding: An α-approximate pricing oracle becomes an η-weak index-finding oracle with η = 1/α by maximizing coverage per unit cost.
- Part 2: from index-finding to point-finding: The index-finding oracle is converted into a point-finding oracle over the cost-r simplex Pr, enabling use of the Plotkin–Shmoys–Tardos covering framework.
- Part 3: black-box covering, then binary search on r: For a guessed cost r, the covering routine either certifies approximate coverage or fails, and binary search locates r near OPT using monotonicity.
- Part 3: black-box covering, then binary search on r: Rescaling the returned vector yields a feasible cover with cost at most α(1 + ε + ε^2)OPT.
- Runtime: The complete procedure runs in polynomial time when the relevant bounds and input encoding lengths are polynomially bounded.