Oct, 2010

电流、拉普拉斯系统与无向图最大流快速逼近

PDF
TL;DR本文介绍了一种通过解决一系列电流问题计算最大流的算法，可以在近线性时间内近似计算每个电流，并且可用于计算 s-t 最大流和最小割，得到了比之前更优的时间复杂度，是目前最快的算法。
maximum flowelectrical flowlinear equationslaplacian matrixalgorithm
发现论文，激发创造
  • 无向图近似最大流的几乎线性时间算法及其多商品推广

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

    Apr, 2013

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

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

    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

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

    本研究提供了一种 O (n log^3 n) 算法，用于在具有弧容量、源节点集和汇节点集的 n 节点有向平面图中找到源到汇的最大流。

    May, 2011

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

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

    Aug, 2009

  • 马尔科夫链的近线性时间算法和有向图的新谱基元

    本文提出了一种面向有向图的射影逼近概念，并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架，通过结合近乎线性时间的稀疏化算法，得到求解定向 Laplacian 线性系统的近乎线性时间算法，本算法的时间复杂度优于现有最优解。

    Nov, 2016

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

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

    Jun, 2023

  • 基于流的局部图聚类算法

    本文介绍了一种名为 LocalImprove 的算法，应用于设计更好的本地图分区算法，该算法是首个切割改进算法，具有局部性质，可以在更短的时间内运行，同时与 Andersen 和 Lang 的全局算法具有相同的理论保证，解决了先前基于随机行走算法的图谱划分局部算法存在的问题。

    Jul, 2013

  • 最大割和最小特征值

    本研究提出了一种基于谱分割的近似算法，可以在多项式时间内解决 max cut 问题，并取得了高质量的结果。

    Jun, 2008

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

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

    Aug, 2005