An "Almost-Linear Time" optimizer?

[infogulch]

In Maximum Flow and Minimum-Cost Flow in Almost-Linear Time (video), they present a way to quickly find directed graph flows that optimize for cost and capacity by using a quickly-converging "Newton's method"-like iterative refinement of an incremental data structure to find the optimal flow.

By lowering e-graph expressions to an executable form with clear costs (some assembly language, webassembly perhaps), I wonder if the resulting derivative graph could be fed into such an optimizer described in the paper, optimizing over minimum cycle count and register capacity. If this mapping can work, and this result is valid, and the "early research result with a large constant factor" stage can be overcome and improved, then it looks like this could be a different way to optimize e-graphs that has a "provable" linear-time algorithm.

Thoughts?

[mwillsey]

Interesting! I'm not very well-versed in that domain, so that might be contribution to why I can't make full sense of the connection at the moment. What is the proposed connection between flow and e-graphs?

[CiaranYoung]

That sounds interesting, but there's no open source code