论文标题
通过动态内部点方法动态最大流量
Dynamic Maxflow via Dynamic Interior Point Methods
论文作者
论文摘要
在本文中，我们提供了一种算法，用于维持$（1-ε）$ - 在边缘添加的动态，电容图中的近似最大流量。在$ m $ - 添加到$ n $ node图的序列上，每个边缘都有供应$ o（\ mathrm {poly}（m））$我们的算法在时间$ \ wideHat {o}（m \ sqrt {n} {n} \ cdot cdotε^{ - 1}）$中运行。为了获得此结果，我们设计了动态数据结构，以解决更一般的问题的问题，即在添加边缘添加的动态图中最低成本循环的值时，最多可获得给定阈值$ f $的$ f $（恰好）。在$ n $ node图上的序列$ m $ additions上，每个边缘都有容量$ o（\ mathrm {poly}（m））$和成本$ o（\ mathrm {poly}（m））$我们解决此阈值的最低成本流量问题$ \ \ \ \ \ \ \ \ \ \ \}（m \ sqrt}）$。我们的这两种算法都以很高的可能性与适应性对手成功。我们通过动态来获得最低成本流的几乎线性时间算法来获得这些结果（Chen，Kyng，Liu，Peng，Peng，Probst Gutenberg，Sachdeva 2022），并引入了一种新的动态数据结构，以使最小值的比率保持在未取向的图表中，以维持与高概率相反的相对较高的相对较高的相对者。
In this paper we provide an algorithm for maintaining a $(1-ε)$-approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of $m$-additions to an $n$-node graph where every edge has capacity $O(\mathrm{poly}(m))$ our algorithm runs in time $\widehat{O}(m \sqrt{n} \cdot ε^{-1})$. To obtain this result we design dynamic data structures for the more general problem of detecting when the value of the minimum cost circulation in a dynamic graph undergoing edge additions obtains value at most $F$ (exactly) for a given threshold $F$. Over a sequence $m$-additions to an $n$-node graph where every edge has capacity $O(\mathrm{poly}(m))$ and cost $O(\mathrm{poly}(m))$ we solve this thresholded minimum cost flow problem in $\widehat{O}(m \sqrt{n})$. Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method used to obtain an almost linear time algorithm for minimum cost flow (Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva 2022), and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.
