cs.LGNov 13, 2026

OverclusterDRG: a Deterministic, LP-Free Heuristic for Robust kk-Center

Authors: Rudra Bhardwaj, Rajni Dabas, Neelima Gupta

Abstract

The kk-center problem is a fundamental formulation for metric clustering. However, its min-max objective is highly sensitive to outliers, motivating the Robust kk-Center (RkkC) formulation which permits excluding up to zz points as outliers. Existing algorithms for RkkC suffer from scalability issues: LP rounding relies on fractional relaxations that scale poorly, known combinatorial approximation algorithms are computationally expensive due to radius guessing, and scalable randomized heuristics require exponential trial multipliers to guarantee success. We present OverclusterDRG, a deterministic, LP-free heuristic for RkkC. The algorithm leverages the theoretical insight of farthest-point oversampling -- adding exactly zz extra candidates to the center set to absorb outliers -- followed by a forward-greedy initialization and a 11-swap local search. Evaluations across real-world datasets show that OverclusterDRG attains a mean approximation ratio of 1.147 against fractional LP lower bounds on the UCI Adult dataset, outperforming state-of-the-art baselines in both clustering quality and speed. By avoiding subset-guessing and exponential trial multipliers, it scales smoothly to n=105n=10^5 points where LP solvers and theoretical algorithms become intractable.

Figures & tables

Explore similar work

Apr 13, 2026

Distributionally Robust K-Means Clustering

K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.
Sep 6, 2026

Parameterized and Streaming Algorithms for Euclidean Fair kk-Center Clustering

Motivated by the growing importance of fairness in machine learning, fair kk-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into mm disjoint groups, and the objective is to select kk data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair kk-center with an approximation ratio of 2.7322.732. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of 4.4644.464. These ratios can be further respectively improved to 2.4142.414 and 3.8283.828 with a runtime exponential on kk. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of 4.7324.732, which can be further improved to 4.424.42, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.
May 8, 2026

Simple KNN-Based Outlier Detection Achieves Robust Clustering

Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the \textit{robust k-Means} problem (i.e., kk-Means with outliers), the goal is to remove zz outliers and minimize the kk-Means cost on the remaining points. Despite the close connection between robust kk-Means and outlier detection, both theoretical and empirical understanding of the effectiveness of classic outlier detection heuristics\textit{classic outlier detection heuristics} for robust kk-Means remains limited. In this paper, we prove that under a practical assumption on the optimal cluster sizes, simply removing points with large KK-Nearest-Neighbor distances achieves performance comparable to prior work in terms of approximation guarantees: it yields a constant-factor reduction from robust kk-Means to standard kk-Means, without introducing additional centers or discarding extra outliers, as is commonly required by existing approaches. Empirically, experiments on real-world datasets show that our method outperforms or matches several more sophisticated algorithms in terms of clustering cost and runtime. These results demonstrate that simple KNN-based heuristics can be surprisingly effective for robust clustering, highlighting new opportunities to bridge techniques from outlier detection and clustering.