Minimum cost flows, MDPs, and l1-regression in nearly linear time for dense instances
Minimum cost flows, MDPs, and l1-regression in nearly linear time for dense instances
复制标题
密集实例的近线性时间内的最小成本流、MDP 和 l1 回归
DOI：
10.1145/3406325.3451108
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wang, Di
中科院分区：
文献类型：
--
作者：
van den Brand, Jan;Lee, Yin Tat;Liu, Yang P.;Saranurak, Thatchaphol;Sidford, Aaron;Song, Zhao;Wang, Di
在本文中，我们提供了新的随机算法与改进的运行时间求解双边约束的线性规划。在n-点边图的最小费用流问题的特殊情况下，得到了一个在n（m+n1.5）时间内求解的随机化方法.这改进了先前的最佳运行时间，并且在单位容量最大流的特殊情况下，改进了先前的最佳运行时间，m4/3 +o（1）[Liu-Sidford'20，Kathuria'20]和[Lee-Sidford'14]中关于n-列m-矩阵的n-1-回归问题，行中，我们获得了一种随机化方法，该方法在N（mn+n2.5）时间内计算一个n-近似解。这产生了一种随机方法，该方法计算折扣马尔可夫决策过程的最优策略，其中S状态和每个状态在时间上的动作（S2 A +S2.5）。这些方法改进了以前的最佳运行时间的方法，依赖于问题的参数，这是mn1.5）[Lee-Sidford'15]和mn1.5（S2.5A）[Lee-Sidford'14，Sidford-Wang-Wu-Ye'18]。首先，我们结合[Lee-Song-Zhang'19，Brand et al. 20]得到一个迭代次数接近小维数平方根的鲁棒随机方法。其次，为了实现这种方法，我们提供了动态数据结构，有效地保持近似变量的刘易斯权重，一个基本的重要性衡量矩阵概括杠杆得分和有效的阻力。
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 onn-vertexm-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 ofm4/3 +o(1)[Liu-Sidford’20, Kathuria’20] and Õ(m√n) [Lee-Sidford’14] for sufficiently dense graphs.In the case of ℓ1-regression in a matrix withn-columns andm-rows we obtain a randomized method which computes an є-approximate solution in Õ(mn+n2.5) time. This yields a randomized method which computes an є-optimal policy of a discounted Markov Decision Process withSstates and,Aactions per state in time Õ(S2A+S2.5). These methods improve upon the previous best runtimes of methods which depend polylogarithmically on problem parameters, which were Õ(mn1.5) [Lee-Sidford’15] and Õ(S2.5A) [Lee-Sidford’14, Sidford-Wang-Wu-Ye’18] respectively.To obtain this result we introduce two new algorithmic tools of possible 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’19, Brand et al.’20] 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.