OverclusterDRG: a Deterministic, LP-Free Heuristic for Robust -Center
Abstract
The -center problem is a fundamental formulation for metric clustering. However, its min-max objective is highly sensitive to outliers, motivating the Robust -Center (RC) formulation which permits excluding up to points as outliers. Existing algorithms for RC 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 RC. The algorithm leverages the theoretical insight of farthest-point oversampling -- adding exactly extra candidates to the center set to absorb outliers -- followed by a forward-greedy initialization and a -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 points where LP solvers and theoretical algorithms become intractable.
Figures & tables
| Dataset | Rows Used | Features | Source |
|---|---|---|---|
| UCI Adult | 32,561 | 6 | [ 1 ] |
| Diabetes Indicators | 99,492 | 8 | [ 8 ] |
| Covertype | 30,000 of 581,012 | 10 | [ 2 ] |
| Algorithm | Mean Ratio | Std. Dev. | Min Ratio | Max Ratio | Med. Time (s) | Max Time (s) |
|---|---|---|---|---|---|---|
| LP Oracle | 1.000 | - | 1.000 | 1.000 | 4,586 | 338,755 |
| R C-Gonzalez | 1.280 | 0.049 | 1.197 | 1.370 | 0.002 | 0.02 |
| Ding | 1.235 | 0.032 | 1.179 | 1.331 | 2.22 | 431 |
| Charikar | 1.173 | 0.056 | 1.104 | 1.306 | 3.60 | 564 |
| OC-Greedy | 1.158 | 0.047 | 1.104 | 1.283 | 0.26 | 52 |
| OverclusterDRG | 1.147 | 0.047 | 1.088 | 1.265 | 0.36 | 57 |
| Diabetes | Covertype | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Algorithm | Mean | Std | Min | Max | Algorithm | Mean | Std | Min | Max | |
| R C-Gonzalez | 1.923 | 0.256 | 1.449 | 2.414 | R C-Gonzalez | 1.671 | 0.173 | 1.418 | 1.960 | |
| Ding | 1.227 | 0.048 | 1.143 | 1.330 | Ding | 1.213 | 0.049 | 1.121 | 1.300 | |
| Charikar | 1.201 | 0.044 | 1.145 | 1.313 | Charikar | 1.227 | 0.060 | 1.134 | 1.374 | |
| OverclusterDRG | 1.155 | 0.043 | 1.093 | 1.275 | OverclusterDRG | 1.171 | 0.051 | 1.095 | 1.294 | |
| Comparison | Mean Diff ( ) | -statistic | -value |
|---|---|---|---|
| OverclusterDRG vs R C-Gonzalez | |||
| OverclusterDRG vs Ding | |||
| OverclusterDRG vs Charikar | |||
| OverclusterDRG vs OC-Greedy |
| Algorithm | Exponent | |
|---|---|---|
| R C-Gonzalez | 0.80 | 0.939 |
| Ding (Practical budget) | 1.10 | 0.962 |
| OverclusterDRG | 1.85 | 0.976 |
| Charikar | 2.12 | 0.999 |
| LP Oracle | 3.40 | 0.988 |
| Dataset | Mean Speedup | Median | Min | Max |
|---|---|---|---|---|
| Diabetes ( ) | ||||
| Covertype ( ) |
| OverclusterDRG radius | OverclusterDRG time | Ding time | |
|---|---|---|---|
| 20,000 | 2.060 | 57s | 133s |
| 50,000 | 2.110 | 310s | 900s |
| 99,000 | 2.150 | 1,100s | 3,800s |
| Setting | Within 5% | Mean gap | Max gap |
|---|---|---|---|
| Over picking by | 53/72 | ||
| Over picking by | 69/72 |
Clustering
Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.
See all 377 papers