Shaofeng H.-C. Jiang

collaborators

7 papers

cs.DS2026

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

Fair Clustering in the Sliding Window Model

Vincent Cohen-Addad, Shaofeng H. -C. Jiang, Qiaoyuan Yang +2

We study streaming algorithms for proportionally fair clustering, a notion originally suggested by Chierichetti et. al. (2017), in the sliding window model. We show that although t…

cs.DS2025

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

Shaofeng H. -C. Jiang, Jianing Lou

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