Shaofeng H.-C. Jiang

collaborators

6 papers

cs.DS2025

Fully Dynamic Euclidean k-Means

Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad +3

We consider the Euclidean $k$ -means clustering problem in a dynamic setting, where we have to explicitly maintain a solution (a set of $k$ centers) $S \subseteq R^{d}$ subje…

cs.DS2025

Relative Error Fair Clustering in the Weak-Strong Oracle Model

Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H. -C. Jiang +4

We study fair clustering problems in a setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak or…

cs.DS2025

Fully Scalable MPC Algorithms for Euclidean k-Center

Artur Czumaj, Guichen Gao, Mohsen Ghaffari +1

The $k$ -center problem is a fundamental optimization problem with numerous applications in machine learning, data analysis, data mining, and communication networks. The $k$ -center…

cs.DS2025

Local Search for Clustering in Almost-linear Time

Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou +1

We propose the first \emph{local search} algorithm for Euclidean clustering that attains an $O (1)$ -approximation in almost-linear time. Specifically, for Euclidean $k$ -Means, our a…

cs.DS2025

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case

Shaofeng H. -C. Jiang, Jianing Lou

We devise $ε$ -coresets for robust $(k, z)$ -Clustering with $m$ outliers through black-box reductions to vanilla case. Given an $ε$ -coreset construction for vanilla clustering with s…

cs.DS2025

Faster Approximation Algorithms for k-Center via Data Reduction

Arnold Filtser, Shaofeng H. -C. Jiang, Yi Li +4

We study efficient algorithms for the Euclidean $k$ -Center problem, focusing on the regime of large $k$ . We take the approach of data reduction by considering $α$ -coreset, which is…