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

CardsList
  1. Distributionally Robust K-Means Clustering

    Apr 13, 2026Vikrant Malik, Taylan Kargin, Babak HassibiClusteringDistribution Shift Robustness

  2. Parameterized and Streaming Algorithms for Euclidean Fair kk-Center Clustering

    Sep 6, 2026Zeyu Lin, Chaoqi Jia, Longkun Guo +1ClusteringApproximation Algorithms

  3. Simple KNN-Based Outlier Detection Achieves Robust Clustering

    May 8, 2026Tianle Jiang, Yufa ZhouClustering