87 citations · 862 across the 74 of their papers we have counts for
5 papers · 1 filter
Path Finding II : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem
Yin Tat Lee, Aaron Sidford
In this paper we present an time algorithm for solving the maximum flow problem on directed graphs with edges, vertices, and capacity rat…
Path Finding I :Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves
Yin Tat Lee, Aaron Sidford
In this paper we present a new algorithm for solving linear programs that requires only iterations to solve a linear program with constraints, …
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
Yin Tat Lee, Aaron Sidford
In this paper we show how to accelerate randomized coordinate descent methods and achieve faster convergence rates without paying per-iteration costs in asymptotic running time. In…
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia +1
In this paper, we introduce a new framework for approximately solving flow problems in capacitated, undirected graphs and apply it to provide asymptotically faster algorithms for t…
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford +1
In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses very little of the machiner…