<story><title>Maximum Flow and Minimum-Cost Flow in Almost-Linear Time</title><url>https://arxiv.org/abs/2203.00671</url></story><parent_chain></parent_chain><comment><author>_hl_</author><text>I spent some (too many) months looking into this domain so I can maybe give some context.&lt;p&gt;The astonishing improvement here is that we can compute &lt;i&gt;exact&lt;/i&gt; 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&amp;#x27;s finally here!&lt;p&gt;I&amp;#x27;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.</text></comment>
<story><title>Maximum Flow and Minimum-Cost Flow in Almost-Linear Time</title><url>https://arxiv.org/abs/2203.00671</url></story><parent_chain></parent_chain><comment><author>thomasahle</author><text>Another very cool recent result is &amp;quot;Negative weight single source shortest path in near linear time:
&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;twitter.com&amp;#x2F;danupon&amp;#x2F;status&amp;#x2F;1511639912008888322?t=47eXAvMgEfBjCoL8AR4hgA&amp;amp;s=19&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;twitter.com&amp;#x2F;danupon&amp;#x2F;status&amp;#x2F;1511639912008888322?t=47e...&lt;/a&gt;&lt;p&gt;Surprisingly this result is (in contrast to the max flow result) entirely combinatoric!</text></comment>