57 citations · 84 across the 20 of their papers we have counts for
6 papers · 1 filter
Moderate Dimension Reduction for -Center Clustering
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir
The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via a random linear map, which has become a fundamental technique in many computational settings.…
Fully Dynamic Algorithms for Euclidean Steiner Tree
T-H. Hubert Chan, Gramoz Goranci, Shaofeng H. -C. Jiang +2
The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points in , possibly using points not in …
Fully Scalable MPC Algorithms for Clustering in High Dimension
Artur Czumaj, Guichen Gao, Shaofeng H. -C. Jiang +2
We design new parallel algorithms for clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalabl…
Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Yecheng Xue, Xiaoyu Chen, Tongyang Li +1
-Clustering in (e.g., -median and -means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the class…
Algorithms for the Generalized Poset Sorting Problem
Shaofeng H. -C. Jiang, Wenqian Wang, Yubo Zhang +1
We consider a generalized poset sorting problem (GPS), in which we are given a query graph and an unknown poset that is defined on the same ver…
The Power of Uniform Sampling for -Median
Lingxiao Huang, Shaofeng H. -C. Jiang, Jianing Lou
We study the power of uniform sampling for -Median in various metric spaces. We relate the query complexity for approximating -Median, to a key parameter of the dataset, call…