27 citations · 41 across the 6 of their papers we have counts for
6 papers
Congestion-Approximators from the Bottom Up
Jason Li, Satish Rao, Di Wang
We develop a novel algorithm to construct a congestion-approximator with polylogarithmic quality on a capacitated, undirected graph in nearly-linear time. Our approach is the first…
Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
Monika Henzinger, Jason Li, Satish Rao +1
In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time which he termed near-linear time meaning linear (…
Capacity Releasing Diffusion for Speed and Locality
Di Wang, Kimon Fountoulakis, Monika Henzinger +2
Diffusions and related random walk procedures are of central importance in many areas of machine learning, data analysis, and applied mathematics. Because they spread mass agnostic…
Local Flow Partitioning for Faster Edge Connectivity
Monika Henzinger, Satish Rao, Di Wang
We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic time algorithm. This improves both on the best p…
Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
Di Wang, Michael Mahoney, Nishanth Mohan +1
We provide improved parallel approximation algorithms for the important class of packing and covering linear programs. In particular, we present new parallel -approximate packin…
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
Di Wang, Satish Rao, Michael W. Mahoney
The linear coupling method was introduced recently by Allen-Zhu and Orecchia for solving convex optimization problems with first order methods, and it provides a conceptually simpl…