Minimum cost flows, MDPs, and ℓ <sub>1</sub> -regression in nearly linear time for dense instances
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
Abstract
In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on n-vertex m-edge graphs with integer polynomially-bounded costs and capacities we obtain a randomized method which solves the problem in Õ(m + n1.5) time. This improves upon the previous best runtime of Õ(m √n) [Lee-Sidford’14] and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of m4/3 + o(1) [Liu-Sidford’20, Kathuria’20] and Õ(m √n) [Lee-Sidford’14] for sufficiently dense graphs.
Topics & Concepts
Computer scienceLinear regressionRegressionMathematical optimizationStatisticsMathematicsMachine learningAdvanced Optimization Algorithms ResearchMachine Learning and AlgorithmsComplexity and Algorithms in Graphs