57 citations · 84 across the 20 of their papers we have counts for
20 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…
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…
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 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…
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…
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen, Shaofeng H. -C. Jiang, Robert Krauthgamer
Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in $\mathbb…
Near-optimal Coresets for Robust Clustering
Lingxiao Huang, Shaofeng H. -C. Jiang, Jianing Lou +1
We consider robust clustering problems in , specifically -clustering problems (e.g., -Median and -Means with outliers, where the cost for a given center…
Streaming Facility Location in High Dimension via Geometric Hashing
Artur Czumaj, Arnold Filtser, Shaofeng H. -C. Jiang +3
In Euclidean Uniform Facility Location (UFL), the input is a set of clients in and the goal is to place facilities to serve them, so as to minimize the total cost of…
Online Facility Location with Predictions
Shaofeng H. -C. Jiang, Erzhi Liu, You Lyu +2
We provide nearly optimal algorithms for online facility location (OFL) with predictions. In OFL, demand points arrive in order and the algorithm must irrevocably assign each d…
Coresets for Kernel Clustering
Shaofeng H. -C. Jiang, Robert Krauthgamer, Jianing Lou +1
We devise coresets for kernel -Means with a general kernel, and use them to obtain new, more efficient, algorithms. Kernel -Means has superior clustering capability compared…
Coresets for Clustering with Missing Values
Vladimir Braverman, Shaofeng H. -C. Jiang, Robert Krauthgamer +1
We provide the first coreset for clustering points in that have multiple missing values (coordinates). Previous coreset constructions only allow one missing coordina…
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 ,…
Coresets for Clustering in Excluded-minor Graphs and Beyond
Vladimir Braverman, Shaofeng H. -C. Jiang, Robert Krauthgamer +1
Coresets are modern data-reduction tools that are widely used in data analysis to improve efficiency in terms of running time, space and communication complexity. Our main result i…
Coresets for Clustering in Graphs of Bounded Treewidth
Daniel Baker, Vladimir Braverman, Lingxiao Huang +3
We initiate the study of coresets for clustering in graph metrics, i.e., the shortest-path metric of edge-weighted graphs. Such clustering problems are essential to data analysis a…
Coresets for Clustering with Fairness Constraints
Lingxiao Huang, Shaofeng H. -C. Jiang, Nisheeth K. Vishnoi
In a recent work, [19] studied the following "fair" variants of classical clustering problems such as -means and -median: given a set of data points in and…
Coresets for Ordered Weighted Clustering
Vladimir Braverman, Shaofeng H. -C. Jiang, Robert Krauthgamer +1
We design coresets for Ordered k-Median, a generalization of classical clustering problems such as k-Median and k-Center, that offers a more flexible data analysis, like easily com…
-Coresets for Clustering (with Outliers) in Doubling Metrics
Lingxiao Huang, Shaofeng H. -C. Jiang, Jian Li +1
We study the problem of constructing -coresets for the -clustering problem in a doubling metric . An -coreset is a weighted subset $S\sub…
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
T-H. Hubert Chan, Haotian Jiang, Shaofeng H. -C. Jiang
We present a unified polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) i…