Capacitated clustering asks us to pick $k$ centers (facilities) and assign every point (client) to one, so that total distance is small and no center serves more than its capacity. It appears in placing cell-network servers, warehouses and depots. Theoretical computer science has a large body of algorithms for it with provable guarantees. Their central trick is called pseudo-approximation: the algorithm is allowed to break one constraint slightly, for example by opening $(1+\epsilon)k$ centers or overfilling capacities by a factor $(1+\epsilon)$. Bending the rules this way gets around the fact that the obvious linear-programming (LP) formulation is uselessly loose. None of these algorithms has ever been run. Their guarantees (factors like 288, $69+\epsilon$, or $O(1/\epsilon^5)$) look hopeless on paper, while practitioners use neural or metaheuristic solvers that are fast but come with no guarantee at all.
We propose that the most useful product of this theory is not its rounding algorithms but its strengthened relaxations. These are tighter LP formulations, and their optimal values are provable lower bounds on the true optimum. If we implement those formulations lazily, adding constraints only when the current solution violates them, we expect them to give per-instance lower bounds tight enough to certify how close a fast heuristic's answer is to optimal. The same machinery lets us measure two quantities nobody has measured: how much cost one actually saves by allowing a few extra centers versus slightly overloaded capacities, and how far the theoretical rounding schemes really land from the optimum.
Core Claim
The natural LP for capacitated $k$-median has an unbounded integrality gap. Its fractional optimum can be arbitrarily cheaper than any real solution, even when $(2-\epsilon)k$ centers are allowed. This is the motivating negative result in On Uniform Capacitated k-Median Beyond the Natural LP Relaxation and Approximating capacitated k-median with (1 + ∊)k open facilities. The configuration LP from the latter paper repairs this locally. For small groups $B$ of candidate centers, it requires that the fractional solution restricted to $B$ be a mixture of genuine integer configurations that open at most $\ell$ centers in $B$. The theory solves this with the ellipsoid method over all groups in $n^{O(1/\epsilon)}$ time, which nobody would implement. Our claim is that a cutting-plane version will close most of the natural-LP gap on real and synthetic instances, and that it will close gap that commercial solvers' generic cuts leave open. The cutting-plane version uses only groups chosen by the theory's own bundling step, small $\ell$ (1 to 3), and separation by small integer programs per group. If both hold, a theory-derived bound becomes a practical certificate. Fast heuristics such as Neural Capacitated Clustering could then be audited instance by instance rather than trusted blindly.
The gap measure we will report is
$$\text{gap closed} = \frac{LB_{\text{config}} - LB_{\text{natural}}}{UB_{\text{best}} - LB_{\text{natural}}},$$
where $LB_{\text{natural}}$ is the natural LP value, $LB_{\text{config}}$ is our strengthened bound, and $UB_{\text{best}}$ is the cost of the best feasible solution found by any method. A value near 1 means the strengthened bound nearly certifies the best known solution.
Research Program
The first component is a practical implementation of three relaxations, each stated in a theory paper but never coded. The first is the configuration LP of Approximating capacitated k-median with (1 + ∊)k open facilities. The second is the rectangle LP for uniform capacities from On Uniform Capacitated k-Median Beyond the Natural LP Relaxation. The third is the multi-commodity flow formulation for capacitated facility location from LP-Based Algorithms for Capacitated Facility Location, which adds alternating-path and flow-cover inequalities.
In each case, the ellipsoid method is replaced by a loop that solves the current LP and searches the candidate groups for a violated configuration constraint. The search is a small integer program per group. The loop adds the violated constraint and re-solves. Groups come from the clustering of the fractional solution around representative clients that these papers already use in their analyses. We will report bound strength and running time as functions of $\ell$ and group size, so the choice of these parameters is itself a measured result.
The second component measures the price of each kind of violation. Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation proves that relaxing capacities and relaxing the center count are equivalent up to constants. The proven factors still differ, $O(1/\epsilon^5)$ against $O(\epsilon^{-2}\log(1/\epsilon))$, and the two kinds of violation cost very different things in practice. For each instance and $\epsilon \in \{0, 0.05, 0.1, 0.2\}$, we compute the best bound and best solution in two variants: center count relaxed to $(1+\epsilon)k$, and capacities relaxed to $(1+\epsilon)u_i$. Plotting both against $\epsilon$ gives two cost curves, one per violation type, which we can compare directly.
The third component runs simplified versions of the rounding pipelines on top of our relaxations. These include the bi-point star rounding of Approximating k-median via pseudo-approximation for the uncapacitated case, and the tree-based dependent rounding for the capacitated case. We report their empirical ratio against $LB_{\text{config}}$, which will finally show how far their actual output is from the proven bounds.
The fourth component borrows a methodological lesson from An Empirical Evaluation of k-Means Coresets. That paper showed that standard benchmarks hide failures, and it built a synthetic Kronecker benchmark designed to trap methods. Our analogue embeds the integrality-gap constructions from the capacitated $k$-median theory papers into realistic point clouds. On these instances the natural LP is provably loose, and they serve as stress tests for both heuristics and bounds.
Baselines
The naive reference point is the natural LP lower bound paired with greedy capacity-respecting assignment from k-means++-style seeding. It shows how much a certificate gains over doing nothing. Its expected weakness, an unbounded gap, is exactly what the theory papers prove, so it must be measured rather than assumed.
The strongest competitor for certification is a commercial mixed-integer solver run on the standard formulation with all of its built-in cuts. These include flow-cover cuts, which overlap with the inequalities in LP-Based Algorithms for Capacitated Facility Location. It gets the same wall-clock limit and thread count as our method. We count our method as beating it if, under equal time, our root bound plus any branching yields a smaller certified gap on instances the solver cannot finish. On small instances where the solver proves optimality, its optimum serves as ground truth.
The strongest competitors for solution quality are Neural Capacitated Clustering and HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem. The neural method combines graph and attention scoring with iterative assignment. It reports reaching solutions in roughly 90 seconds versus over 900 seconds for traditional solvers on Shanghai Telecom and Telecom Italia Milan, a 5x to 10x speedup. No reported clustering-cost value was found on Lacuna for those datasets. HA-CCP is a variable-neighborhood metaheuristic. It reports the best average solution on 58 of 90 instances, with 217.25 seconds average runtime on RanReal240/480. Neither approach is a rival certificate. We run them under their published settings with equal tuning budgets, and we judge our contribution by whether we can tell, per instance, how good their answers are. A secondary target is whether our relaxation-guided rounding, used as a warm start, matches their cost.
The key ablation isolates the configuration constraints. We run the identical loop and solver with only natural LP constraints plus generic cuts, and then add configuration constraints at $\ell = 1, 2, 3$. If the gap closed does not grow with $\ell$, the theory's main idea adds nothing in practice.
Why not just…?
Why not just run a commercial integer-programming solver to optimality? On instances of a few hundred points this may well work, and it is a real threat to the certification claim at that scale. We use it there as ground truth rather than as a rival. The open question is the regime of thousands of clients with tight, uneven capacities, where branch-and-bound may stall because the root bound is weak. The equal-time comparison in the baselines settles this directly. If generic solver cuts already match the configuration bound, we will report that the theory's relaxations are redundant in practice. That would be a useful negative result.
Why not just use the neural or metaheuristic solvers, which are faster? We do use them. Neither one tells the user how far a returned solution is from optimal. HA-CCP's own authors report that it is inferior to NDVNS on the largest MDG-a instances, a failure only visible because a competing method existed. Our certificates make such failures visible without needing one. The gap-embedded stress instances test whether these solvers fail silently where theory predicts hardness.
Why not just use local search, which already has a guarantee of 5 for capacitated facility location? LP-Based Algorithms for Capacitated Facility Location notes this bound is much smaller than its own 288. However, local search yields no per-instance lower bound, and its guarantee does not cover hard-capacitated $k$-median with non-uniform capacities. We include a swap-based local search as a solution baseline. Our bounds will tell whether its real gap is closer to 1 or to 5.
Proposed Experiments
The instance families are as follows. Shanghai Telecom and Telecom Italia Milan are converted to capacitated $k$-median, following the preprocessing of Neural Capacitated Clustering: base stations become clients, traffic becomes demand, and candidate sites become centers. Capacitated vehicle routing instances serve as clustering problems. Synthetic 2D Gaussian mixtures have capacity tightness swept from loose to near-infeasible and capacities from uniform to highly skewed. The gap-embedded stress family is described above. The RanReal and MDG-a suites optimize within-cluster edge weight rather than distance to centers, so we use them only for runtime scaling of the separation loop, not for $k$-median gap claims.
The metrics are gap closed, certified ratio (heuristic cost divided by our best lower bound), wall-clock time, and the two price-of-violation curves. The study has three decisive checks. First, on solver-optimal instances, configuration constraints must close a clearly larger share of the natural-LP gap than generic cuts alone. Second, on the large telecom instances, our bound must certify the best heuristic within a few percent where the solver alone leaves a wide gap. Third, empirical rounding ratios must be compared against the proven factors. If the first check fails, the central claim is false, and the paper becomes a negative measurement of how far these celebrated relaxations sit from practice.
References
- On Uniform Capacitated $k$-Median Beyond the Natural LP Relaxation
- Approximating capacitated k-median with (1 + ∊)k open facilities
- Neural Capacitated Clustering
- LP-Based Algorithms for Capacitated Facility Location
- Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation
- Approximating k-median via pseudo-approximation
- An Empirical Evaluation of k-Means Coresets
- HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem