16 citations · 61 across the 32 of their papers we have counts for
42 papers
Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs
Jason Li, Trevor Vaughn
A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let be a positively weighted -vert…
Beyond the Quadratic Time Barrier for Network Unreliability
Ruoxu Cen, William He, Jason Li +1
Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running ti…
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Ruoxu Cen, William He, Jason Li +1
We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose additio…
A Local Search-Based Approach for Set Covering
Anupam Gupta, Euiwoong Lee, Jason Li
In the Set Cover problem, we are given a set system with each set having a weight, and we want to find a collection of sets that cover the universe, whilst having low total weight.…
On the Fixed-Parameter Tractability of Capacitated Clustering
Vincent Cohen-Addad, Jason Li
We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best…
Edge Connectivity Augmentation in Near-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an -time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms…