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