1 citations · 1 across the 2 of their papers we have counts for
6 papers · 1 filter
The Power of Arrival Times in Random-Order Online Facility Location
Yichen Huang, Shaofeng H. -C. Jiang
We study online metric facility location with uniform opening costs in the random-order model (Meyerson FOCS'01). The best previous upper bound was a -competitive randomized alg…
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.…
Dimension Reduction for Clustering: The Curious Case of Discrete Centers
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir +2
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of points into dimension with low…
Near-Optimal Dimension Reduction for Facility Location
Lingxiao Huang, Shaofeng H. -C. Jiang, Robert Krauthgamer +1
Oblivious dimension reduction, Ã la the Johnson-Lindenstrauss (JL) Lemma, is a fundamental approach for processing high-dimensional data. We study this approach for Uniform Facilit…
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…
Streaming Algorithms for Geometric Steiner Forest
Artur Czumaj, Shaofeng H. -C. Jiang, Robert Krauthgamer +1
We consider an important generalization of the Steiner tree problem, the \emph{Steiner forest problem}, in the Euclidean plane: the input is a multiset ,…