Explanipedia

Coresets for Robust Clustering via Black-Box Reductions to Vanilla Case Open

Shaofeng H.-C. Jiang, Jianing Lou · 2025

We devise ε-coresets for robust (k,z)-Clustering with m outliers through black-box reductions to vanilla clustering. Given an ε-coreset construction for vanilla clustering with size N, we construct coresets of size N⋅ polylog(kmε^{-1}) + O…

Streaming Algorithms for Geometric Steiner Forest Open

Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý · 2024

We consider a generalization of the Steiner tree problem, the Steiner forest problem , in the Euclidean plane: the input is a multiset $X\subseteq{\mathbb{R}}^{2}$ , partitioned into $k$ color classes $C_{1},\ldots,C_{k}\subseteq X$ …

Online Facility Location with Predictions Open

Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, Yubo Zhang · 2021

We provide nearly optimal algorithms for online facility location (OFL) with predictions. In OFL, $n$ demand points arrive in order and the algorithm must irrevocably assign each demand point to an open facility upon its arrival. The objec…

Coresets for Kernel Clustering Open

Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang · 2021

We devise coresets for kernel $k$-Means with a general kernel, and use them to obtain new, more efficient, algorithms. Kernel $k$-Means has superior clustering capability compared to classical $k$-Means, particularly when clusters are non-…

Coresets for Clustering with Missing Values Open

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu · 2021

We provide the first coreset for clustering points in $\mathbb{R}^d$ that have multiple missing values (coordinates). Previous coreset constructions only allow one missing coordinate. The challenge in this setting is that objective functio…

SPIN: BSP Job Scheduling With Placement-Sensitive Execution Open

Zhenhua Han, Haisheng Tan, Shaofeng H.-C. Jiang, Wanli Cao, Xiaoming Fu , et al. · 2021

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently due to the popularity of computations as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct…

Coresets for Clustering in Excluded-minor Graphs and Beyond Open

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu · 2021

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 is a fast algorithm to construct a small coreset for k-Media…

Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation Open

Zhenhua Han, Haisheng Tan, Shaofeng H.-C. Jiang, Xiaoming Fu, Wanli Cao , et al. · 2020

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrent…

Coresets for Clustering in Excluded-minor Graphs and Beyond Open

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu · 2020

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 is a fast algorithm to construct a small coreset for k-Media…

A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics Open

T-H. Hubert Chan, Haotian Jiang, Shaofeng H.-C. Jiang · 2020

We present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a…

Coresets for Clustering in Graphs of Bounded Treewidth Open

D. N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer , et al. · 2019

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 and used for example in road networks and data visualization…

Coresets for Clustering with Fairness Constraints Open

Lingxiao Huang, Shaofeng H.-C. Jiang, Nisheeth K. Vishnoi · 2019

In a recent work, [19] studied the following "fair" variants of classical clustering problems such as $k$-means and $k$-median: given a set of $n$ data points in $\mathbb{R}^d$ and a binary type associated to each data point, the goal is t…

Coresets for Ordered Weighted Clustering Open

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu · 2019

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 combining multiple objectives (e.g., to increase fairness or f…

Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics Open

Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu · 2018

We study the problem of constructing epsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An epsilon-coreset is a weighted subset S subset of X with weight function w : S -> R->= 0, such that for any k-subset C …

$\varepsilon$-Coresets for Clustering (with Outliers) in Doubling Metrics Open

Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu · 2018

We study the problem of constructing $\varepsilon$-coresets for the $(k, z)$-clustering problem in a doubling metric $M(X, d)$. An $\varepsilon$-coreset is a weighted subset $S\subseteq X$ with weight function $w : S \rightarrow \mathbb{R}…

A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in\n Doubling Metrics Open

T-H. Hubert Chan, Haotian Jiang, Shaofeng H.-C. Jiang · 2017

We present a unified polynomial-time approximation scheme (PTAS) for the\nprize collecting traveling salesman problem (PCTSP) and the prize collecting\nSteiner tree problem (PCSTP) in doubling metrics. Given a metric space and a\npenalty f…

Online Submodular Maximization Problem with Vector Packing Constraint Open

T-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, Xiaowei Wu · 2017

We consider the online vector packing problem in which we have a $d$ dimensional knapsack and items $u$ with weight vectors $\mathbf{w}_u \in \mathbb{R}_+^d$ arrive online in an arbitrary order. Upon the arrival of an item, the algorithm m…

Optimal Decomposition Strategy For Tree Edit Distance Open

Shaofeng H.-C. Jiang · 2017

An ordered labeled tree is a tree where the left-to-right order among siblings is significant. Given two ordered labeled trees, the edit distance between them is the minimum cost edit operations that convert one tree to the other.\nIn this…

Online Submodular Maximization Problem with Vector Packing Constraint Open

T-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, Xiaowei Wu · 2017

We consider the online vector packing problem in which we have a d dimensional knapsack and items u with weight vectors w_u in R_+^d arrive online in an arbitrary order. Upon the arrival of an item, the algorithm must decide immediately wh…

Approximation schemes for network design problems in doubling metrics Open

Shaofeng H.-C. Jiang · 2017

Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids Open

T-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang · 2017

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying …

A PTAS for the Steiner Forest Problem in Doubling Metrics Open

T-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang · 2016

We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean plane in [FOCS 2008: Borradaile, Klein and Mathieu]. Our PTAS…

Shaofeng H.-C. Jiang YOU? Author Swipe