Researchers achieve ‘absurdly fast’ algorithm for network flow(quantamagazine.org)
quantamagazine.org
Researchers achieve ‘absurdly fast’ algorithm for network flow
https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/
79 comments
So basically they took a greedy algorithm that used a combinatorial approach and transformed it to use a calculus approach by inspiring from a related problem of "electrical flow through a network".
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.
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.
In this case the "greedy" algorithm was guaranteed to give the best possible flow in the network so this speedup applies to the optimal solution. I think in a lot of cases greedy algorithms are used when the alternative is an NP-hard problem like bin packing or TSP for which we might be looking at speeding up an already sub-optimal solution.
Can anyone recommend a 'friendly' overview of the 'calculus approach'?
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.
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.
Isn't the Quanta article supposed to be the 'friendly' overview?
It's lacking. Their explanation for the greedy algo is great, less so for every other. By the end of the article, their 'explanations' degrade to speed analogies.
If I have the names right, your parent is looking for the derivation of "Optimal Power Flow", and its linearization "Linear/DC OPF".
If I have the names right, your parent is looking for the derivation of "Optimal Power Flow", and its linearization "Linear/DC OPF".
There are classes of problems for which greedy algorithms are known to provide optimal solutions. An example is maximum matching on bipartite graphs. This is related to combinatorial structures called matroids (and an extension called greedoids.)
https://en.wikipedia.org/wiki/Greedoid
https://en.wikipedia.org/wiki/Greedoid
Yea maybe for related problems (but not all optimization problems in general).
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.
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.
Linear electrical networks have no maximum current, though.
Nice! Now this would be expected algo from candidates in google/meta interviews, especially for senior IC roles.
Update your leetcode answers folks.
Update your leetcode answers folks.
I've been wondering if there is a connection between Lagrangian Mechanics/Calculus of Variations and Dijkstra's shortest path algorithm.
https://profoundphysics.com/lagrangian-mechanics-for-beginne... How you would translate from the discrete, relational approach to the continuous, analytic one?
https://profoundphysics.com/lagrangian-mechanics-for-beginne... How you would translate from the discrete, relational approach to the continuous, analytic one?
Keywords: Optimal Control, Bellman. I'm serious.
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.
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.
To expand on these themes, you may be interested in reading up on these & related topics:
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...
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...
Susskind seems to think that Kolmogorov complexity is deeply related to quantum gravity: https://m.youtube.com/watch?v=6OXdhV5BOcY
I hadn't seen a Susskind lecture before. This is cool.
He reminds me of Jonathon Banks. I feel like I'm getting a physics lecture from Mike Ehrmantraut :)
He reminds me of Jonathon Banks. I feel like I'm getting a physics lecture from Mike Ehrmantraut :)
[deleted]
From a layperson perspective maybe something like Fermat's Principle is what you are curious about. It also seems one can usually encode/send combinatorial problems into some other space or representation and decode them back into the discrete world. Generating functions and such.
[deleted]
Previous HN discussion: https://news.ycombinator.com/item?id=31149038
> Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
> 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.
https://arxiv.org/abs/2203.00671
> 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.
https://arxiv.org/abs/2203.00671
I've been out of school for a while, what does m^(1+o(1)) mean?
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"?
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"?
No. Any constant is in O(1), but not in o(1). Specifically, f=O(g) means f is (eventually) at most Cg for a certain C, but f=o(g) means f is (eventually) at most Cg for all C.
A useful, albeit not really rigorous, way to think about this is O is like ≤, while o is like <.
A useful, albeit not really rigorous, way to think about this is O is like ≤, while o is like <.
o(1) is "little O" notation, where for a function y = o(f), y(x) / f(x) --> 0 as x --> infinity. In other words, y goes to 0 faster than f. In this context, m^(1 + o(1)) means roughly that you converge to linear time for large m.
I wish we could all collectively agree that using = for the o/O/etc. notations is stupid and stop this. These are sets of functions. f is not equal to the set, it is an element of the set and we already have a well defined notation for that: f ∈ o(...). So use that or use the LateX f \in o(...) if you want to restrict yourself to ASCII. Using = only serves to confuse.
(some descriptive linguistics) People often think of "=" as "is", when "is" can convey both equality and possession of an attribute. IIRC there was an article about how American kids think "=" means "the answer is" because they first encountered it with equations like 5+5=10. I've also seen people write 2x+5=10 = 2.5, meaning "the answer to the problem 2x+5=10 is 2.5"
Or, rather, it grows more slowly than m^(1 + epsilon) for any fixed epsilon > 0.
The function m log m is m^(1 + o(1)) but it grows more quickly than linear.
The function m log m is m^(1 + o(1)) but it grows more quickly than linear.
The notation means that it must be faster than m^t for any t strictly greater than one. Basically, it means that you can have any number of log factors on the running time, so it could be m*log(m)^1000
I'm sorry, but I'm pretty sure you are wrong there. m^(log(log(m))/log(m)) = log(m), and log(log(m))/log(m) is certainly not o(1) since it's nondecreasing (and that's just a single logarithm). I'm pretty sure o(1) requires your slowdown over linear to be faster asymptotically than any iterated logarithm, (so faster than log(log(m)), log(log(log(m))), etc.), which is close enough to linear time that calling it "almost linear" seems quite accurate!
log(log(m))/log(m) tends to zero as m tends to infinity, which is what it means to be o(1). It is decreasing for m > e^e.
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.
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.
Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1).
For an example, consider 2^sqrt(log(n)).
This is a bit similar to something being faster than polynomial, but slower than exponential.
For an example, consider 2^sqrt(log(n)).
This is a bit similar to something being faster than polynomial, but slower than exponential.
Thanks for the clarification! I didn't mean to say the two definitions were equivalent, as indeed they aren't. Rephrasing my second point to (hopefully) eliminate the ambiguity: There are two non-equivalent popular definitions for "almost linear" or "nearly linear" (n^(1+o(1)) and O(n log^k(n)), and nevertheless classifying "n log^1000 n" as almost linear is uncontroversial in the sense that both of the common definitions do it.
(The second paragraph of my original message addressed a point made in the parent's second paragraph, which has since been edited out.)
(The second paragraph of my original message addressed a point made in the parent's second paragraph, which has since been edited out.)
Oh, so it is. I retract my comment. In that case it seems like a pretty stupid designation to me.
The o(1) here represents a decreasing function in m, such as 1/m. (Note: This is little o, not big o.)
Therefore, for any k > 1: m^(1+o(1)) grows more slowly than m^k but faster than m
Therefore, for any k > 1: m^(1+o(1)) grows more slowly than m^k but faster than m
It means m^(1+eps) for arbitrarily small positive constant epsilon. So you can make it run in time O(m^1.1) but also in time O(m^1.00000001), where the latter will presumably have a larger constant implied by the O().
The technical reason you can make eps arbitrarily small is that it represent a function of m that tends to 0 as m tends to infinity.
Mhh, while what you are saying is not wrong (though I'm not convinced about the constant thing, given everything is asymptotic), it's a bit imprecise.
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
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
[deleted]
The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.
> based on your luck
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.
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.
Is there an implementation and benchmark for this? Skimming, it appears to be built upon many theoretical results, any one of which could require impractical problem sizes or machine memory. In my head, the term ‘absurdly fast’ implies a computational result rather than theory. Also, I don’t see many echoes of the Spielman paper which seems to be the focus of the article, and is a lot more understandable in my opinion.
Years ago I came up with the first algorithm to solve a problem in a niche area in polynomial time. It uses some fairly contrived techniques; the power of the polynomial, if we really tried to estimate it, would probably have been >=10, or even >=20. But some time later another group of researchers expanded a technique used in the algorithm to help solve the problem in a much more practical manner.
From TFA it appears this is not practical yet, maybe in the future:
> 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.
> 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.
I highly recommend Francis Spufford’s excellent Red Plenty, a very unusual book that combines soviet economics and computer science into a fictional narrative that centers upon this and other related problems.
Great article. Nitpick: I don't know why they repeatedly talked about linear time being related to "the time it takes to write it down". Well, I sort of do, but I feel that it's a little misleading, as people unfamiliar with the term might think it's more closely linked to writing than it is.
I imagine they're trying to say you can't have a sub-linear approach, because it takes linear time to specify the graph (going over it once). So the time to "write it down" is the best you can possibly do (for an exact method).
Amazing
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?
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?
This is remarkable. We live in amazing times.
Link to the paper
https://arxiv.org/abs/2203.00671
https://arxiv.org/abs/2203.00671
As always with any of these kind of computational speed related posts, I just want to know what it means for audio related applications and latency
Reading the article I wondered if anyone tried to model the network flow using dynamics of the fluids. And if he did, what were the results.
Looking at the opening picture: is it allowed to fly a drone over busy traffic?
Depends on the country's laws, the pilot certifications, the drone in question, the airspace that intersection sits on, and sometimes on the land owner.
There will be combinations of these where it's allowed.
There will be combinations of these where it's allowed.
It ALSO does minimum cost?
Is this academically published?
Is this newer than the various links that date to 2010?
Is this academically published?
Is this newer than the various links that date to 2010?
The link to the paper is n the 1st paragraph:
https://arxiv.org/abs/2203.00671
https://arxiv.org/abs/2203.00671
And the PDF here: https://arxiv.org/pdf/2203.00671v2.pdf
Hope someone makes a package for it.
Not a comment in regard to this article in particular, but I love Quanta Magazine. Just the right amount of detail for a non-scientist and consistently fascinating subject matter.
I don't. Most Quanta articles have this pattern: they pepper the article with quotes from famous professors and only mention the authors in the middle of the page. I suppose one could argue this provides context and is a kind of attestation to the importance/relevance of the work. But I don't think this is right.
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.
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.
I also find Quanta articles rarely satisfactory with respect to the historical and social aspects of science (culture, ideas, experiments, interest...) but prioritizing explaining research and concepts over talking about people is a well justified editorial choice for a scientific magazine.
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.
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.
You are right in general, but when the quote is from someone on whose research the result builds in an important way (as it is the case here), I would say it is fair.
Same here. I love that they also cover maths, which few pop sci publications do.
I'd agree with you ~1 year ago but I think a lot of their articles now tend to water-down lots of complex subjects in rigorous math papers. Still remains one of my favorite websites.
i think they have to water it down so much because hardly anyone would understand the math, even people who consider themselves good at math or have degrees in STEM..it's just so advanced even relative to that .
I think this is probably right. They are among the few to even attempt it.
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.
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.
Yeah this is me. No advanced STEM background so just barely hanging on by a thread. I enjoy being immersed in topics I don’t understand but I get more out of it with a little something to hang on to.
[deleted]
Coming to a coding interview near you!
Yes, only those who can intuitively discover this algorithm are fit to write HTML and JS at this company.
lol, coding interviews are truly absurd
[deleted]