Researchers achieve ‘absurdly fast’ algorithm for network flow
quantamagazine.org
quantamagazine.org
I wonder if it isn't possible to do this for other greedy algorithms, or algorithms which are trying to find optimal solutions through heuristics.
It looks like this solution works for a specific group of problems. So it won't be applicable to all problems that use greedy (or other) heuristics.
The paper linked in the article from 2003/2008 has been split up into 3 rather technical articles - I was hoping for something easier that just gave me a flavour of the method.
If I have the names right, your parent is looking for the derivation of "Optimal Power Flow", and its linearization "Linear/DC OPF".
Update your leetcode answers folks.
https://profoundphysics.com/lagrangian-mechanics-for-beginne... How you would translate from the discrete, relational approach to the continuous, analytic one?
He reminds me of Jonathon Banks. I feel like I'm getting a physics lecture from Mike Ehrmantraut :)
For a first exercise, forget Dijkstra and just solve a maze by doing Value Iteration, and plot the cost-to-go at each step.
Then consider that this function doesn't have to take a graph vertex or grid cell, but could instead be some continuous function on R^n.
The next step usually is to learn about the Linear Quadratic Regulator problem, where the cost-to-go is a quadratic, and you get to do an iteration of "Value Iteration" by updating the quadratic coefficients.
To connect to physics, see how you'd write the Action Integral in these terms.
Hamilton-Jacobi-Bellman equation: https://en.wikipedia.org/wiki/Hamilton%E2%80%93Jacobi%E2%80%...
Pontryagin maximum principle: https://en.wikipedia.org/wiki/Pontryagin%27s_maximum_princip...
> We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m^(1+o(1)) time. Our algorithm builds the flow through a sequence of m^(1+o(1)) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized m^o(1) time using a new dynamic graph data structure.
^ Our framework extends to algorithms running in m^(1+o(1)) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.
Isn't any constant trivially in "o(1)"? So m^1000 is in this class?
Or are they using it informally to mean "a very small number"?
The function m log m is m^(1 + o(1)) but it grows more quickly than linear.
Therefore, for any k > 1: m^(1+o(1)) grows more slowly than m^k but faster than m
A useful, albeit not really rigorous, way to think about this is O is like ≤, while o is like <.
Besides n^(1+o(1)), the other common definition for "almost linear" is precisely O(n log^k (n)) for some k, no matter how large.
For an example, consider 2^sqrt(log(n)).
This is a bit similar to something being faster than polynomial, but slower than exponential.
(The second paragraph of my original message addressed a point made in the parent's second paragraph, which has since been edited out.)
A more exact formulation would be m^(1+o(1)) is equal to m^(1 + eps(m)) for some eps where eps(m) -> 0 for m -> infty
Uh, no, based on the size of your input. o(1) means something that goes to 0 as m gets bigger, it has nothing to do with randomness.
> For now, it’s primarily a theoretical advance, since the speed improvements kick in only for networks that are far larger than the ones we encounter in the real world, for which maximum flow problems can already be solved fairly quickly (at least, if they don’t involve minimizing costs). But pieces of the new algorithm might see practical use within a year, predicted Richard Peng of the University of Waterloo in Canada, one of the algorithm’s six creators. And in the coming years, researchers said, computer scientists will likely find ways to make it more practical and perhaps even slightly faster.
Are we gonna see a lot of derived papers, where someone picks any old paper that uses a flow algorithm to solve task X and then presents the new result, we can improve the runtime of solving task X with the new flow algorithm?
There will be combinations of these where it's allowed.
Is this academically published?
Is this newer than the various links that date to 2010?
As someone who loves math but who only knows a little, I find the articles manage to convey the broad ideas quite well. What it is, why it matters. I could stand more detail, but I guess many others couldn't.
To me, I want to know who the authors are in the first paragraph. They deserve the credit. The famous professor quotes should come later.
In this case there is a link to the article in the first paragraph and as the article discusses the whole history of maximum flow finding the new and exciting developments in the second half is quite reasonable.