论文标题
在几乎线性的时间内最大流量和最小成本流量
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
论文作者
论文摘要
我们提供了一种算法，该算法在有向图上计算出$ m $边缘的有向图上的最大成本流以及多项式界限的积分需求，成本和能力，价格为$ M^{1+o（1）} $时间。我们的算法通过$ m^{1+o（1）} $近似无向的最小比率周期的顺序构建流量，每个序列都使用新的动态图数据结构进行计算和处理。 我们的框架扩展到以$ M^{1+O（1）} $计算流量的时间运行的算法，以最大程度地将一般边缘分离的凸功能最小化至高精度。这为几个问题提供了几乎线性的时间算法，包括熵登记的最佳传输，矩阵缩放，$ p $ - norm流量和$ p $ - norm等速频率回归。
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, $p$-norm flows, and $p$-norm isotonic regression on arbitrary directed acyclic graphs.
