Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow

By Yin Tat Lee, Aaron Sidford. IEEE Annual Symposium on Foundations of Computer Science, 2014

351 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, neutral): “…. 10 4.2 Challenges in Improving Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Our Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14”
Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear Running Time (2017, background): “3729) √ |S| log 1 [19] Combinatorial Interior Point Algorithm |S|4|A|4 log |S| 1−γ [29] Algorithm 1 for general DMDP Õ( |S| 3|A| (1−γ)4 2 ) Corollary 1 Algorithm 1 for ergodic DMDP Õ( |S||A| (1−γ)2 2 ) Corollary 2”
Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time (2017, methodology): “5|A|L) [20] Combinatorial Interior Point Algorithm |S|4|A|4 log |S| 1−γ [31] Phased Q-Learning Õ(|S|2|A| + |S|2|A| + |S||A| (1−γ)6 2 ) [18] and This Work Randomized Primal-Dual Method Õ( |S| (3)|A| (1−γ)6 2 ) Main Result 1 Randomized Primal-Dual Method Õ(|S|2|A| + |S||A| (1−γ)4 2 ) under ergodicity ”
Geometric median in nearly linear time (2016, methodology): “We begin by noting the Hessian is approximately a scaled identity minus a rank 1 matrix.”