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

Would love a tldr if anyone has a link.

Np=p

,, 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

Coming to a software engineering interview near you!

I've just skimmed, but the paper is quite unkind about its internal details (which is very typical for mathies, hahaha).

I think the algorithm is non-exact. Say, Theorem 1.1 explicitly mentions probability:

> There is an algorithm that, on a graph G = (V, E) with m edges, vertex demands, edge costs, and upper/lower edge capacities, all integral and bounded by U in absolute value, computes an exact min-cost flow in m1+o(1) log2 U time with high probability.

(See how their "theorem" is much easier to understand than the abstract...)

This is a kind of advanced algorithm with a sprinkle of optimization, so normal dudes won't be able to get a grasp on this easily. Also, this is too much for my caffeinated Monday morning.