按年被提到
20222022 · 4 次2026
算法与数据结构›经典算法与数据结构·arXiv:2203.00671 · cs.DS

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

几乎线性时间的最大流与最小费用流
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva · 2022

m^(1+o(1)) 时间求精确最大流与最小费用流的算法

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 6 人首次 2022-03-02 · 最近 2024-06-30发表于 Annual Symposium on Foundations of Computer Science
6不同的人
5活跃月份
6讨论串
136被引(OpenAlex)

论文给出在 m 条边的有向图上、在需求、费用和容量为多项式有界整数时,以 m^(1+o(1)) 时间精确计算最大流和最小费用流的算法。做法是通过一系列近似无向最小比率圈逐步构造流,每个圈借助一种新的动态图数据结构在摊还 m^(o(1)) 时间内处理;框架还能推广到边可分离的一般凸函数,给出熵正则最优传输、矩阵缩放、p 范数流等问题的几乎线性时间算法。

HN 为什么提它

评论者把它当作最近的几乎线性时间最大流结果来引用,例如在讨论细粒度复杂度、P 类问题的进展时举例,也有人指出完整预印本比会议版本更详细。

方法难度 5 / 5约 240 分钟经得起时间
读之前最好知道
1最大流与最小费用流
2图算法与复杂度分析
3内点法(interior point methods)
4动态图数据结构
5凸优化

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用thorncorona · 2022-06

“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.”

转引摘要:以 m^(1+o(1)) 时间精确求解最大流和最小费用流
Researchers achieve ‘absurdly fast’ algorithm for network flow原评论 ↗
引用eynsham · 2023-02

“for example, the recent result on max flow.”

拿最近的最大流结果作为细粒度 P 类问题的例子
Why Sat Is Hard原评论 ↗
引用vitus · 2024-06

“Preprint at Maximum Flow and Minimum-Cost Flow in Almost-Linear Time”

指出这是完整预印本,含详细界,ACM 版本是缩略版
Researchers develop the fastest possible flow algorithm原评论 ↗
被提交为 story · 3 次