24 citations · 151 across the 43 of their papers we have counts for
6 papers · 2 filters
Better Sparsifiers for Directed Eulerian Graphs
Sushant Sachdeva, Anvith Thudi, Yibin Zhao
Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. Directed Laplacian linear sy…
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…
Fast Algorithms for Separable Linear Programs
Sally Dong, Gramoz Goranci, Lawrence Li +2
In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A promi…
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, Rasmus Kyng +5
We give a deterministic time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral dem…
A Simple and Efficient Parallel Laplacian Solver
Sushant Sachdeva, Yibin Zhao
A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linea…
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Gramoz Goranci, Monika Henzinger, Harald Räcke +2
Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polyl…