Another very cool recent result is "Negative weight single source shortest path in near linear time: https://twitter.com/danupon/status/1511639912008888322?t=47e...
Surprisingly this result is (in contrast to the max flow result) entirely combinatoric!
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!
,, 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:
Coming to a software engineering interview near you!
Does anyone know if these algorithms are practical on real problems on real machines, or is the constant term large enough you would normally just use a more traditional algorithm for most work?
What does $m^{1 + O(1)}$ time mean exactly? This could be m^5000 for all we knew. How is this almost-linear, and how can it be guaranteed?
Anyone know enough to tell if this can be used to calculate sparsest cut?
Would love a tldr if anyone has a link.
undefined
Np=p
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.