57 citations · 157 across the 32 of their papers we have counts for
15 papers · 1 filter
On Coresets for Clustering in Small Dimensional Euclidean Spaces
Lingxiao Huang, Ruiyuan Huang, Zengfeng Huang +1
We consider the problem of constructing small coresets for -Median in Euclidean spaces. Given a large set of data points , a coreset is a much smaller set…
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…
Improved Coresets for Clustering with Capacity and Fairness Constraints
Lingxiao Huang, Pinyan Lu, Xuan Wu
We study coresets for clustering with capacity and fairness constraints. Our main result is a near-linear time algorithm to construct -sized $\va…
Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
Lingxiao Huang, Jian Li, Pinyan Lu +1
Designing small-sized \emph{coresets}, which approximately preserve the costs of the solutions for large datasets, has been an important research direction for the past decade. We…
On Optimal Coreset Construction for Euclidean -Clustering
Lingxiao Huang, Jian Li, Xuan Wu
Constructing small-sized coresets for various clustering problems in different metric spaces has attracted significant attention for the past decade. A central problem in the cores…
Efficient Submodular Optimization under Noise: Local Search is Robust
Lingxiao Huang, Yuyi Wang, Chunxue Yang +1
The problem of monotone submodular maximization has been studied extensively due to its wide range of applications. However, there are cases where one can only access the objective…
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…
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 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…
Capacitated Center Problems with Two-Sided Bounds and Outliers
Hu Ding, Lunjia Hu, Lingxiao Huang +1
In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices , we want to find a subset of vertices , called centers, s…
Canonical Paths for MCMC: from Art to Science
Lingxiao Huang, Pinyan Lu, Chihao Zhang
Markov Chain Monte Carlo (MCMC) method is a widely used algorithm design scheme with many applications. To make efficient use of this method, the key step is to prove that the Mark…
Approximation Algorithms for the Connected Sensor Cover Problem
Lingxiao Huang, Jian Li, Qicai Shi
We study the minimum connected sensor cover problem (MIN-CSC) and the budgeted connected sensor cover (Budgeted-CSC) problem, both motivated by important applications (e.g., reduce…
-Kernel Coresets for Stochastic Points
Lingxiao Huang, Jian Li, Jeff M. Phillips +1
With the dramatic growth in the number of application domains that generate probabilistic, noisy and uncertain data, there has been an increasing interest in designing algorithms f…
Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
Lingxiao Huang, Jian Li
We consider the stochastic geometry model where the location of each node is a random point in a given metric space, or the existence of each node is uncertain. We study the proble…