算法与理论计算机2022arxiv.org编辑精选
近线性时间内的最大流与最小费用流
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
专业 · 约 120 分钟读完前置知识：图论基础、最大流/最小费用流问题、算法复杂度分析
导读
这篇论文给出了最大流与最小费用流的近线性时间精确算法，是理论计算机科学的重要突破。此前已有近线性时间计算近似最优流的算法，而该工作首次实现了精确解，作者还指出框架可推广到最小化一般边可分凸函数的高精度流计算。
HN 关注点：这一理论突破：最大流是经典基础问题，从近似最优到精确最优的近线性算法是长期期待的结果；讨论焦点是理论意义与实际可用性的差距。
后来怎么样
这是理论计算机科学的重要突破，首次给出最大流与最小费用流的近线性时间精确算法，引出了后续一系列关于图算法（如负权最短路径）的近线性时间研究工作。
HN 评论精选
这几条评论里：补充 3 亲历 1
补充解释突破点在于精确流而非近似流，但因常数巨大短期内难以实用
我花了好几个月研究这个领域，可以提供一些背景。这里惊人的改进是可以在近线性时间内计算精确流。此前近线性时间计算近似最优流的算法已存在一段时间，因此有人最终找到近线性时间求最优流的算法是意料之中的——现在终于来了！我只粗读了论文，作者似乎借鉴了为近似最优情形建立的一套技术，这些技术常数非常大，所以短期内不太可能有实用的实现。
_hl_查看英文原文
I spent some (too many) months looking into this domain so I can maybe give some context. The astonishing improvement here is that we can compute exact flows in almost-linear time. Previous algorithms for computing almost-optimal flows in almost-linear time have been known for some time, and hence it was expected that someone would eventually find an algorithm that finds optimal flows in almost-linear time. Well, looks like it's finally here! I've only skimmed the paper but it seems to me that the authors draw on a set of techniques established for the almost-optimal case. These come with rather enormous constants, so it is unlikely that there will be a practical implementation of this algorithm any time soon.
补充补充相关新成果：负权最短路径近线性算法，且是纯组合方法
另一个很酷的近期成果是“负权单源最短路径的近线性时间算法”。令人惊讶的是，这个结果（与最大流结果不同）完全是组合式的！
thomasahle查看英文原文
Another very cool recent result is "Negative weight single source shortest path in near linear time: https://twitter.com/danupon/status/1511639912008888322?t=47eXAvMgEfBjCoL8AR4hgA&s=19 Surprisingly this result is (in contrast to the max flow result) entirely combinatoric!
亲历从业者视角：期待该算法在车辆路径等实际问题中的应用价值
我做过与图算法相关的 VRP（车辆路径问题）工作——这个看起来非常有意思，真希望当年就有这个算法！
voz_查看英文原文
I worked on graph and graph-ish algorithms for the VRP (https://en.wikipedia.org/wiki/Vehicle_routing_problem) - this looks super interesting, wish we had this back then!
补充指出该框架可能改进闪电网络最优路径路由算法
论文提到“我们的框架可扩展到 m^(1+o(1)) 时间的算法，以高精度计算最小化一般边可分凸函数的流”。这看起来是对 Rene Pickhart 当前闪电网络最优路径算法的一个有趣改进可能，很想知道他怎么看。
xiphias2查看英文原文
,, Our framework extends to an algorithm running in m1+o(1) time for computing flows that minimize general edge-separable convex functions to high accuracy.'' This looks like an interesting improvement possibility over the current algorithm for optimal pathfinding over the Lightning Network by Rene Pickhart, it would be interesting to know what he thinks about it: https://arxiv.org/abs/2107.05322
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2022Hacker News 讨论帖230 分 · 40 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选