Faster maxflow via improved dynamic spectral vertex sparsifiers
Faster maxflow via improved dynamic spectral vertex sparsifiers
复制标题
通过改进的动态光谱顶点稀疏器加快最大流速度
DOI：
10.1145/3519935.3520068
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sidford, Aaron
中科院分区：
文献类型：
--
作者：
van den Brand, Jan;Gao, Yu;Jambulapati, Arun;Lee, Yin Tat;Liu, Yang P.;Peng, Richard;Sidford, Aaron
我们在经历动态电阻更新的加权图中的电流的维持方面取得了几个广泛相关的进展，包括：(1)更有效的动态谱顶点稀疏，通过使用Morris计数器对加权图中的随机游动的长度进行更快的估计来实现[Morris 1978，Nelson-Yu 2020]。(2)从检测动态电流中具有大能量的边到动态谱顶点稀疏器的直接简化。(3)将估计来自不经意的对手的更新下的向量序列的算法从差分隐私转变为通过高斯机制容忍自适应对手的算法。将这些片段与对先前健壮内点框架的修改相结合，给出了一个算法，该算法在图上计算具有边代价和容量的最小代价流，时间为[1，U](M3/2−1/58log2U)。在以前的独立工作中，[Axiotis-MąDry-Vladu FOCS2021]也得到了一种求解有能力图上稀疏最小费用流的改进算法。该算法改进了[Gao-Liu-Peng FOCS2021]中的Ao(m~3/2−1/58logU)时间最大流算法，改进了[Gao-Liu-Peng−2021]的O(m~3/2 FOCS1/328logU)时间最大流算法。
We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including:(1) More efficient dynamic spectral vertex sparsification, achieved by faster length estimation of random walks in weighted graphs using Morris counters [Morris 1978, Nelson-Yu 2020].(2) A direct reduction from detecting edges with large energy in dynamic electric flows to dynamic spectral vertex sparsifiers.(3) A procedure for turning algorithms for estimating a sequence of vectors under updates from an oblivious adversary to one that tolerates adaptive adversaries via the Gaussian-mechanism from differential privacy.Combining these pieces with modifications to prior robust interior point frameworks gives an algorithm that on graphs withmedges computes a mincost flow with edge costs and capacities in [1,U] in timeO(m3/2−1/58log2U). In prior and independent work, [Axiotis-Mądry-Vladu FOCS 2021] also obtained an improved algorithm for sparse mincost flows on capacitated graphs. Our algorithm implies aO(m3/2−1/58logU) time maxflow algorithm, improving over theO(m3/2−1/328logU) time maxflow algorithm of [Gao-Liu-Peng FOCS 2021].
登录
查看更多内容
超稀疏超稀疏器和更快的拉普拉斯系统求解器
DOI：
10.1137/1.9781611976465.33
发表时间：
2021
期刊：
SODA 2021
影响因子：
--
作者：
Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron
具有次多项式最坏情况更新时间的动态最小生成森林
DOI：
10.1109/focs.2017.92
发表时间：
2017
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Danupon Nanongkai;Thatchaphol Saranurak;Christian Wulff
通讯作者：
Christian Wulff
当前矩阵乘法时间的确定性线性规划求解器
DOI：
10.1137/1.9781611975994.16
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Jan van den Brand
通讯作者：
Jan van den Brand
DOI：
10.1145/3406325.3451056
发表时间：
2020-11
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Sally Dong;Y. Lee;Guanghao Ye
通讯作者：
Sally Dong;Y. Lee;Guanghao Ye
一种新的递减单源最短路径算法及其在顶点容量流和切割问题中的应用
DOI：
10.1145/3313276.3316320
发表时间：
2019
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Julia Chuzhoy;S. Khanna
通讯作者：
S. Khanna