Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
复制标题
嵌套剖析与 IPM 的结合：近线性时间内的平面最小成本流
DOI：
10.1137/1.9781611977073.7
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ye Guanghao
中科院分区：
文献类型：
--
作者：
Dong, Sally;Gao, Yu;Goranci, Gramoz;Lee, Yin Tat;Peng, Richard;Sachdeva, Sushant;Ye Guanghao
我们提出了一个近似线性的时间算法，找到一个最小费用流的平面图多项式有界的整数成本和容量。以前这个问题的最快算法是基于内点方法（IPM），并在O（n1.5poly（logn））时间内对一般稀疏图起作用[Daitch-Spielman，STOC'08]。直觉上，Ω（n1.5）是基于IPM的方法的自然运行时障碍，因为它们需要迭代，每次路由可能密集的电流。为了打破这一障碍，我们开发了一个新的隐式表示流的基础上广义嵌套解剖[Lipton-Rose-Tarjan，JSTOR'79]和近似舒尔补[Kyng-Sachdeva，FOCS'16]。这种隐式表示允许我们设计一个数据结构来路由一个稀疏需求的电力流在大致的更新时间，导致总的运行时间为O（n· poly（logn））。我们的结果立即扩展到所有的家庭的可分图。
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem was based on interior point methods (IPMs) and worked for general sparse graphs inO(n1.5poly(logn)) time [Daitch-Spielman, STOC'08].Intuitively, Ω(n1.5) is a natural runtime barrier for IPM based methods, since they require iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested-dissection [Lipton-Rose-Tarjan, JSTOR'79] and approximate Schur complements [Kyng-Sachdeva, FOCS'16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly update time, resulting in a total running time ofO(n· poly(logn)).Our results immediately extend to all families of separable graphs.