Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances
Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances
复制标题
密集实例的近线性时间内的最小成本流、MDP 和 ℓ1 回归
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Di Wang
中科院分区：
文献类型：
--
作者：
Jan van den Brand;Yin Tat Lee;Yang P. Liu;Thatchaphol Saranurak;Aaron Sidford;Zhao Song;Di Wang
在本文中，我们提供了具有改进的运行时间的新随机算法，用于求解具有两侧约束的线性程序。在具有整数多项式有界成本和容量的 n 顶点 m 边图上的最小成本流问题的特殊情况下，我们获得了一种在 Õ(m + n1.5) 时间内解决该问题的随机方法。这改进了之前的最佳运行时间 Õ(m √n) [Lee-Sidford’14]，并且在单位容量最大流量的特殊情况下，改进了之前的最佳运行时间 m4/3 + o(1) [Liu-Sidford’20，Kathuria’20] 和 Õ(m √n) [Lee-Sidford’14]，以获得足够密集的图。对于 n 列 m 行矩阵中的 ℓ1 回归，我们获得了一种随机方法，该方法在 Õ(mn + n2.5) 时间内计算 є 近似解。这产生了一种随机方法，该方法计算具有 S 个状态的贴现马尔可夫决策过程的 є 最优策略，并且每个状态的 A 个动作及时 Õ(S2 A + S2.5)。这些方法改进了之前的最佳运行时间，这些方法以多对数方式依赖于问题参数，分别为 Õ(mn1.5) [Lee-Sidford'15] 和 Õ(S2.5 A) [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 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. In the case of ℓ1-regression in a matrix with n-columns and m-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 with S states and, A actions per state in time Õ(S2 A + 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.5 A) [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.
登录
查看更多内容
中等密集图上近线性时间的二分匹配
DOI：
10.1109/focs46700.2020.00090
发表时间：
2020
期刊：
2020
影响因子：
--
作者：
van den Brand, Jan;Lee, Yin-Tat;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol;Sidford, Aaron;Song, Zhao;Wang, Di
通讯作者：
Wang, Di
DOI：
10.1287/opre.2023.2451
发表时间：
2020-05
期刊：
Oper. Res.
影响因子：
--
作者：
Gen Li;Yuting Wei;Yuejie Chi;Yuantao Gu;Yuxin Chen
通讯作者：
Gen Li;Yuting Wei;Yuejie Chi;Yuantao Gu;Yuxin Chen
DOI：
10.1145/3357713.3384247
发表时间：
2019-10
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Yang P. Liu;Aaron Sidford
通讯作者：
Yang P. Liu;Aaron Sidford
DOI：
10.4230/lipics.icalp.2022.20
发表时间：
2020-04
期刊：
ArXiv
影响因子：
--
作者：
A. Bernstein;Jan van den Brand;M. Gutenberg;Danupon Nanongkai;Thatchaphol Saranurak;Aaron Sidford;He Sun
通讯作者：
A. Bernstein;Jan van den Brand;M. Gutenberg;Danupon Nanongkai;Thatchaphol Saranurak;Aaron Sidford;He Sun
DOI：
10.1109/focs46700.2020.00018
发表时间：
2020-03
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Kyriakos Axiotis;Aleksander Mkadry;Adrian Vladu
通讯作者：
Kyriakos Axiotis;Aleksander Mkadry;Adrian Vladu