Approximation-Preserving Consistent Clustering with Optimal Deletion Guarantees

Online clustering must adapt as new points arrive. Even a single insertion can trigger many center replacements. Consistent clustering seeks a good solution at every step while limiting center recourse, the total number of new centers introduced over time. For insertion-only $(k,z)$-clustering, including $k$-median and $k$-means, Chan et al. (2025) convert an offline $\alpha$-approximation into an online algorithm, but the approximation factor becomes $(1+\epsilon ){\alpha }^2$. We improve this factor to $(1+\epsilon )\alpha$ for arbitrarily small $\epsilon$, preserving the quality of the offline solver while retaining controlled recourse. The central difficulty is freeing room for new centers before knowing which old centers a future solution can reuse. Our BudgetDelete routine frees capacity within a prescribed cost budget, without an additional clustering oracle, and provides a deletion guarantee that holds for every comparison solution. This guarantee is tight in its budget and geometric separation parameters, up to constants depending on $z$. Local cost comparisons at multiple distance scales then certify when old centers can replace newly computed ones with little additional cost. On a common weighted-epoch interface, the exponent of $1/\epsilon$ in the proved recourse bound decreases from $6$ to $3$ for $k$-median and from $14$ to $5$ for $k$-means. To isolate the cost of accuracy, we consider a single center with points arriving at consecutive integer locations on the real line. Even in this elementary setting, maintaining near-optimal squared loss requires accuracy-dependent recourse, for which we establish matching upper and lower bounds. On three UCI datasets with $k\in \{5,10,20\}$, our practical variant uses one shared parameter setting and reduces accumulated smoothed coreset cost by $1.9\%$ to $10.1\%$ and center recourse by $4.0\%$ to $41.0\%$ relative to the released Chan et al. (2025) heuristic, with lower recorded update-loop computation.