Jiayang Ren
Research

Global Optimal Clustering

Contents
  1. Overview
  2. Publications

K-Medoids and K-Center clustering solved to global optimality on up to one billion samples.

Overview

I developed reduced-space spatial branch-and-bound algorithms for K-Medoids and K-Center clustering, with customized lower bounds, bound tightening, and sample reduction, accelerated on hybrid CPU–GPU hardware. They solve problems with up to one billion samples to global optimality, scaling 250× (K-Medoids) and 200,000× (K-Center) beyond earlier exact methods, with over 20% better objectives than widely used heuristics.

K-Medoids and K-Center clustering, the spatial branch-and-bound framework, and dataset sizes solvable to global optimality
(a) K-Medoids and K-Center clustering. (b) The spatial branch-and-bound framework only branches on the region of medoids. (c) Dataset sizes solvable to global optimality.

Publications

Manag. Sci. 2026

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

Ren, J., You, N., Hua, K., Ji, C., and Cao, Y.

Management Science, 72(6): 5106–5130 (2026).

DOI
NeurIPS 2022

Global Optimal K-Medoids Clustering of One Million Samples

Ren, J., Hua, K., and Cao, Y.

Advances in Neural Information Processing Systems, 35: 982–994 (2022).

PDFProceedings
ICML 2022

Global Optimization of K-Center Clustering

Shi, M., Hua, K., Ren, J., and Cao, Y.

International Conference on Machine Learning, PMLR 162: 19956–19966 (2022).

PDFProceedings