16 citations · 61 across the 32 of their papers we have counts for
5 papers · 1 filter
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…
Near-Linear Time Approximations for Cut Problems via Fair Cuts
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +1
We introduce the notion of {\em fair cuts} as an approach to leverage approximate -mincut (equivalently -maxflow) algorithms in undirected graphs to obtain near-linea…