# A Global Optimization Algorithm for K-Center Clustering of One Billion Samples

arXiv: https://arxiv.org/abs/2301.00061 · HTML: https://mlsanity.com/paper/2301.00061/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 47 references that are in the map.
- First posted on arXiv 30 Dec 2022.

## Builds on (most cited first, 3 of 3)

- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [The Parameterized Hardness of the k-Center Problem in Transportation Networks](https://mlsanity.com/paper/1802.08563/) (2018)

## Built on by (most cited first, 1 of 1)

- [Continual Learning with Elastic Regularization and Synthetic Replay for Federated MLLM Fine-Tuning](https://mlsanity.com/paper/2607.12112/) (2026)

## Abstract (arXiv)

This paper presents a practical global optimization algorithm for the K-center clustering problem, which aims to select K samples as the cluster centers to minimize the maximum within-cluster distance. This algorithm is based on a reduced-space branch and bound scheme and guarantees convergence to the global optimum in a finite number of steps by only branching on the regions of centers. To improve efficiency, we have designed a two-stage decomposable lower bound, the solution of which can be derived in a closed form. In addition, we also propose several acceleration techniques to narrow down the region of centers, including bounds tightening, sample reduction, and parallelization. Extensive studies on synthetic and real-world datasets have demonstrated that our algorithm can solve the K-center problems to global optimal within 4 hours for ten million samples in the serial mode and one billion samples in the parallel mode. Moreover, compared with the state-of-the-art heuristic methods, the global optimum obtained by our algorithm can averagely reduce the objective function by 25.8% on all the synthetic and real-world datasets.