75 citations · 200 across the 26 of their papers we have counts for
9 papers · 1 filter
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…
Almost All Even Yao-Yao Graphs Are Spanners
Jian Li, Wei Zhan
It is an open problem whether Yao-Yao graphs (also known as sparse-Yao graphs) are all spanners when the integer parameter is large enough. In this paper we sho…
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…
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li +2
In this paper, we consider the fault-tolerant -median problem and give the \emph{first} constant factor approximation algorithm for it. In the fault-tolerant generalization of c…
Matroid and Knapsack Center Problems
Danny Z. Chen, Jian Li, Hongyu Liang +1
In the classic -center problem, we are given a metric graph, and the objective is to open nodes as centers such that the maximum distance from any vertex to its closest cent…