Dynamic Maxflow via Dynamic Interior Point Methods
Dynamic Maxflow via Dynamic Interior Point Methods
复制标题
DOI：
10.1145/3564246.3585135
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Jan van den Brand;Y. Liu;Aaron Sidford
中科院分区：
文献类型：
--
作者：
Jan van den Brand;Y. Liu;Aaron Sidford
在这篇文章中，我们提供了一个算法来维持一个动态的，有容量的图在边插入过程中保持一个(1−є)近似的最大流。对于n结点图的m次插入序列，其中每条边的容量为O(Poly(M))，我们的算法运行时间为O(m√n·є−1)。为了得到这一结果，我们为更一般的检测问题设计了动态数据结构，即对于给定的阈值F，在进行边插入的动态图中，最小代价循环的值何时达到最大值F(准确地)。在n结点图的m个插入序列中，其中每条边都有容量O(Poly(M))和代价O(Poly(M))，我们在O(m√n)中解决了这个阈值最小代价流问题。我们的两种算法在对抗适应性对手时都有很高的成功概率。我们通过对[Chen等人最近提出的内点方法进行动态化处理得到这些结果。Focs 2022]用于获得求解最小费用流的几乎线性时间算法，并引入了一种新的动态数据结构来维护无向图中的最小比率循环，该无向图在对抗自适应攻击时以高概率成功。
In this paper we provide an algorithm for maintaining a (1−є)-approximate maximum flow in a dynamic, capacitated graph undergoing edge insertions. Over a sequence of m insertions to an n-node graph where every edge has capacity O(poly(m)) our algorithm runs in time O(m √n · є−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 insertions achieves value at most F (exactly) for a given threshold F. Over a sequence m insertions to an n-node graph where every edge has capacity O(poly(m)) and cost O(poly(m)) we solve this thresholded minimum cost flow problem in O(m √n). Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method by [Chen et al. FOCS 2022] used to obtain an almost linear time algorithm for minimum cost flow, and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.