Clustering is a cornerstone of unsupervised learning, yet traditional methods like $k$-means often struggle with imbalanced data where cluster densities vary significantly. The $k$-center problem addresses this by minimizing the maximum distance between any data point and its nearest center (a "minimax" objective), making it robust to class imbalance. However, the problem is NP-hard, and finding globally optimal solutions has historically been limited to small datasets of a few thousand points.
Presented at AAAI-23, this research introduces kc-Opt, the first algorithm capable of finding globally optimal solutions for generalized $L_1$ $k$-center clustering on datasets with up to one million points.
The kc-Opt Framework
The kc-Opt algorithm overcomes the computational barriers of exact clustering through three primary innovations:
- Generalized $L_1$ Formulation: By adopting the $L_1$ (Manhattan) distance, the authors formulate the clustering objective as a Mixed Integer Linear Program (MILP). Unlike $L_2$ (Euclidean) formulations, which lead to harder quadratic programs, the linear nature of $L_1$ allows the use of highly optimized commercial solvers like Gurobi.
- Constraint Generation: A standard MILP for $N$ points requires $N \times K$ constraints, which is intractable for large $N$.
kc-Optutilizes an iterative approach: it starts with a small subset of points, solves the MILP, identifies the most "violated" points (those furthest from current centers) in the full dataset, and adds them as new constraints. This process repeats until global optimality is reached. - Outlier Robustness (
kc-OptOut): Standard $k$-center clustering is highly sensitive to noise. The authors extended their MILP to allow $l$ points to remain unassigned, effectively ignoring outliers during optimization.
Key Insights: The Boundary Advantage
A critical insight of this work is that the optimal centers in $k$-center clustering are determined solely by the "extreme" points on the boundaries of clusters. Points located in the cluster interior do not influence the final radius. This "boundary insight" explains why kc-Opt can solve a million-point problem while only ever processing a few hundred constraints at a time. For a synthetic dataset of 1,000,000 points, the algorithm reached the global optimum using only approximately 450 generated constraints.
Experimental Results
The authors evaluated kc-Opt against popular greedy baselines, such as Gonzalez’s algorithm (kc-Gon) and Hochbaum-Shmoys (kc-HS), across 20 real-world benchmark datasets (e.g., Iris, Adult, Skinsegment) and large-scale synthetic data.
Performance Highlights:
- Superior Accuracy: In many real-world cases, greedy approximations yielded objective values nearly double the true optimum found by
kc-Opt. - Unprecedented Scale: The algorithm successfully optimized a synthetic dataset of 1,000,000 points across 15 clusters, a feat previously impossible for exact solvers.
- Noise Handling: The
kc-OptOutvariant demonstrated the ability to recover ground-truth cluster centers even in heavily contaminated datasets, where standard algorithms were significantly skewed by outliers.
Conclusion and Future Directions
kc-Opt demonstrates that global optimality in $k$-center clustering is achievable at scale by combining MILP with constraint generation. While currently optimized for $L_1$ distance, future work may explore extending these techniques to $L_2$ distance via Mixed-Integer Quadratically Constrained Programming (MIQCP) or developing automated methods for estimating the optimal number of outliers ($l$).
Summary updated