论文标题
嵌套的解剖符合IPM：平面微分以在几乎线性的时间内
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
论文作者
论文摘要
我们提出了一种几乎线性的时间算法，用于在多项式整数成本和容量的平面图中找到最低成本的流量。此问题的先前最快算法基于内部点方法（IPM），适用于$ O（n^{1.5} \ text {poly}（\ log n））$ time [daitch-spielman，stoc'08]中的常规稀疏图。从直觉上讲，$ω（n^{1.5}）$是基于IPM的方法的自然运行时屏障，因为它们需要$ \ sqrt {n} $迭代，每个迭代都可能会路由可能密度密度的电流。 为了打破这一障碍，我们为基于广义嵌套 - 拆卸[Lipton-Rose-Tarjan，Jstor'79]的流量开发了新的隐式表示，并近似Schur补充[Kyng-Sachdeva，focs'16]。这种隐式表示允许我们设计一个数据结构，以大约$ \ sqrt {n} $更新时间来路由稀疏需求的电流，从而导致总运行时间为$ O（n \ cdot \ cdot \ text {poly} {poly}（\ log log n））$。 我们的结果立即扩展到所有可分离图的家庭。
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 is based on interior point methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\text{poly}(\log n))$ time [Daitch-Spielman, STOC'08]. Intuitively, $Ω(n^{1.5})$ is a natural runtime barrier for IPM-based methods, since they require $\sqrt{n}$ 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 $\sqrt{n}$ update time, resulting in a total running time of $O(n\cdot\text{poly}(\log n))$. Our results immediately extend to all families of separable graphs.
