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 $\tilde{O}(m+n^{1.5})$ time. This improves upon the previous best runtime of $\tilde{O}(m\sqrt{n})$ (Lee-Sidford 2014) and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of $m^{4/3+o(1)}$ (Liu-Sidford 2020, Kathuria 2020) and $\tilde{O}(m\sqrt{n})$ (Lee-Sidford 2014) for sufficiently dense graphs. For $\ell_1$-regression in a matrix with $n$-columns and $m$-rows we obtain a randomized method which computes an $\epsilon$-approximate solution in $\tilde{O}(mn+n^{2.5})$ time. This yields a randomized method which computes an $\epsilon$-optimal policy of a discounted Markov Decision Process with $S$ states and $A$ actions per state in time $\tilde{O}(S^2A+S^{2.5})$. These methods improve upon the previous best runtimes of methods which depend polylogarithmically on problem parameters, which were $\tilde{O}(mn^{1.5})$ (Lee-Sidford 2015) and $\tilde{O}(S^{2.5}A)$ (Lee-Sidford 2014, Sidford-Wang-Wu-Ye 2018). To obtain this result we introduce two new algorithmic tools of independent interest. First, we design a new general interior point method for solving linear programs with two sided constraints which combines techniques from (Lee-Song-Zhang 2019, Brand et al. 2020) to obtain a robust stochastic method with iteration count nearly the square root of the smaller dimension. Second, to implement this method we provide dynamic data structures for efficiently maintaining approximations to variants of Lewis-weights, a fundamental importance measure for matrices which generalize leverage scores and effective resistances.
翻译:在本文中, 我们提供新的随机算法, 改进运行时间, 以双向限制解决线性程序 。 在美元- 顶价美元- 美元- 顶价美元- 顶价图表上的最低成本流量问题的特殊例子中, 我们获得了一个随机化方法, 解决 $tilde{ (m+n ⁇ 1.5} 美元/ 美元) 的问题。 这比上次最高级运行时间 $\ tilde{ (m\\ sqrt{ O} (m\ sqrt{ } 美元) 更好。 在美元- 西德福尔德的参数上, 美元- 最低成本- 美元最大流量的最小成本流动问题。 在美元- 单位能力最大流动的特殊例子中, 之前的最佳运行时间 $m@4/3+ 美元( Kathuria 2020) 和 美元- 美元- complidforderal 的计算方法。 以美元- 美元- 美元- 美元- 美元- 快速化的计算方法, 我们用此方法来改进了 美元- 美元- 快速化的流程的流程 方法。