May, 2011

有向平面图中多源多汇最大流的近线性时间算法

PDF
TL;DR本研究提供了一种 O (n log^3 n) 算法，用于在具有弧容量、源节点集和汇节点集的 n 节点有向平面图中找到源到汇的最大流。
maximum flowplanar graphalgorithmarc capacitiessource and sink nodes
发现论文，激发创造
  • 电流、拉普拉斯系统与无向图最大流快速逼近

    本文介绍了一种通过解决一系列电流问题计算最大流的算法，可以在近线性时间内近似计算每个电流，并且可用于计算 s-t 最大流和最小割，得到了比之前更优的时间复杂度，是目前最快的算法。

    Oct, 2010

  • 无向图近似最大流的几乎线性时间算法及其多商品推广

    该论文提出了一种新的框架来近似解决容量限制下的流问题，并将其应用于提供渐进更快的最大流问题和最大并发多商品流问题的算法，该算法优化了现有的时间复杂度，并给出了多个新的技术工具如非欧几里得梯度下降、流加密器以及近似线性的路由机制。

    Apr, 2013

  • 寻路 II：最小费用流问题 Õ(m sqrt (n)) 算法

    本论文提出了一种新的内点法来处理最大流问题，该算法通过将其应用于线性规划制定最大流、最小费用流和有损广义最小费用流的问题，并借鉴 Daitch 和 Spielman 的方法分析，最终在 O (m√nlogO (1)(U/ε)) 的时间内解决这些问题，同时在使用 Spielman 和 Peng 的 Laplacian 系统求解器进行并行化后，达到了 O (√nlogO (1)(U/ε)) 和 O (m√nlogO (1)(U/ε)) 的时间。

    Dec, 2013

  • 在近线性时间内求解近似最大流

    介绍了一种新的方法来解决最大流问题，使用 alpha-congestion-approximators 在无向，容量图中，通过计算简单的函数，维护任意流来优化拥挤度，并提出使用类似 Spielman and Teng （STOC 2004）解决 Laplacian 系统问题的方法。

    Apr, 2013

  • 多智能体路径规划与网络流

    通过将基于图的多智能体路径规划与网络流问题相连接，本文研究表明前者可以归纳为后者，进而实现了组合网络流算法及一般线性规划技术应用于基于图的多智能体路径规划问题。此外，在研究中我们还证明了当目标具有排列不变性的情况下，问题仅有一个可行解路径集，该集合具有不超过 $n+V-1$ 的最大完成时间，并提供了一个完整的算法以在 $O (nVE)$ 时间内找到这样的解决方案。最后，我们研究了可行解的时间和距离优化，表明它们具有成对帕累托优化结构，并提供了优化这两个实际目标的有效算法。

    Apr, 2012

  • 利用流和重新加权特征值进行有向图划分的快速算法

    提供了一种基于对称正定半定规划的指向图划分算法，同时证明了此算法具备较好的扩展性。

    Jun, 2023

  • 匹配和网络流的量子算法

    本研究提出了三种不同的量子算法，可以解决最大二分匹配问题，最大非二分匹配问题以及整数网络中的最大流问题。

    Aug, 2005

  • 顶点稀疏化：旧技术的新结果

    本文提出了一种构建图的方法，可以在保持相对低的阻塞情况下在终端之间支持多元流动，并且可以通过凸组合方法构建特定类型的图，并通过解决 0-extension 问题来证明结果并推广到更广泛的图。

    Jun, 2010

  • 对于稀疏割的 sqrt (log (n))- 逼近，打破多商品流的障碍

    本文提出一种同时实现在子二次时间内运行和找到稀疏切分的算法，并使用特定算法而不是黑盒求解器来解决多商品流网络中的好路径问题。该算法实现了 O (sqrt (log (n)/eps)) 的近似和 O (n^epslog^ O (1) n) 的最大流复杂度。同时，我们还展示了切割匹配游戏框架不能实现更好的近似，除非重新路由流。

    Aug, 2009

  • 近线性时间内求解稠密图中的最小费用流、MDPs 和 L1 回归

    本文提出了两个新的算法工具，一个内点法用于解决具有双侧约束的线性规划问题，另一个是动态数据结构，用于有效地维护 Lewis 权重的近似值，从而改进了解决最小费用流和 l1 回归问题的随机算法的效率，提高了计算优化决策过程的方法的效率。

    Jan, 2021