6 citations · 19 across the 16 of their papers we have counts for
26 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.…
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…
Augmenting Edge Connectivity via Isolating Cuts
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS '20). Our algorithm uses poly-logarit…
Approximate Gomory-Hu Tree Is Faster Than Max-Flows
Jason Li, Debmalya Panigrahi
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting mincuts (and by duality, the values of maxflows) for all pairs of ver…
Deterministic Weighted Expander Decomposition in Almost-linear Time
Jason Li, Thatchaphol Saranurak
In this note, we study the expander decomposition problem in a more general setting where the input graph has positively weighted edges and nonnegative demands on its vertices. We…