Researchers develop the fastest possible flow algorithm
ethz.chThe algorithm is near linear asymptotically at the limit when n -> inf.
In the end of video they tell there is no way that any implementation of their algorithm gets close to beating existing algorithms in the real world.
https://cacm.acm.org/research/almost-linear-time-algorithms-...
So it's another galactic algorithm?
I imagine the point of this algorithm, like a lot of algorithm research, is to prove the upper bound of complexity for this problem. Not to be used in practice (despite what this article seem to suggest).
On a similar note, there's a lot of work put into optimal matrix multiplication algorithm. We know the lower bound is N*2, the obvious upper bound is N*3, the best (complexity wise, not practical at all) current algorithm is N*2.37, but we don't know how fast can it really get. Is it possible to write N*2 algorithm? We don't know.
Both N^2 and N*2 are fine, but N*2 should really not mean what you want it to mean…
Now reading my comment again, I probably understand what happened. I typed N*2, and yet it showed as N*2. Probably this is why.
I mean nobody is stopping me from writing an exponential time algorithm.
Knowing an upper bound means you know that the best solution for the problem takes at most that much work. It does not mean that you can’t find worse solutions.
Sure? If you're slow on purpose that doesn't affect the upper bound set by the "obvious" method.
I think they’re replying to the claimed upper bound of n^3. I’m not actually sure what that means.
see schoolbook algorithm for the n^3 bound: https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
It comes from directly applying the definition of matrix multiplication on a square matrix.
I'm not sure how to phrase this better than saying it's the bound set by the obvious method. Are you familiar with the obvious method of multiplying a matrix? It's n operations for each cell, and you have n^2 cells.
Being worse on purpose is always possible, but it doesn't change that bound.
It's the "obvious" upper bound, not the "how did you even get here without noticing the obvious method" upper bound.
Thank you for introducing a term and concept I was not familiar with.
From that page:
> Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.
Are there examples of Galactic Algorithms that now aren't Galactic Algorithms?
edit: turns out some matmul algorithms are?
I was about to ask if there was a term for this
That's a let down after all the hype in the opening pages.
I have to say that when I saw the headline I was extremely skeptical. "Fastest possible" is a very, very bold claim.
yeah, and another caveat tends to be with these kinds of cases is that you nearly need the absolute optimum - something that gets a 99% in 1% the time tends to be much more practical
Interestingly, the same guy also works on making 'theory-only' algorithms work well in practice [1]. But, it seems like that takes another 20 years -- [1] is building on a theory breakthrough from 2004 [2], but these algorithms are only starting to work in practice in 2024, IIUC. I guess that means there's hope for practical min-cost flow algorithms in 2044.
> Almost-Linear-Time Algorithm
From O(mn) to O(m) ... thus excluding N (number of vertices) from computation ...
Too good to be true?
Constant factor so large it's going to be slower than existing (asymptotically worse) algorithms on any practical inputs.
Still, a neat theoretical result.
The constant factors could be optimized or even accelerated with special-purpose hardware. There could be a simplification or even something like reuse/caching/memoization that in real world will reduce the constant factor significantly.
Maybe, but that would be a different research project.
The constant factors are currently so large that even multiple orders of magnitude speedups would not make this practical.
> A glance at the raw figures shows just how far we have come: until the turn of the millennium, no algorithm managed to compute faster than m1.5, where m stands for the number of connections in a network that the computer has to calculate, and just reading the network data once takes m time. In 2004, the computing speed required to solve the problem was successfully reduced to m1.33. Using Kyng’s algorithm, the “additional” computing time required to reach the solution after reading the network data is now negligible.
TFA didn’t describe Kyng’s breakthrough in terms of this mscore it considers so important. What’s up with that?
Sometimes I think we have lost the plot completely with complexity as a metric. Increasingly we are seeing algorithms which have optimized the complexity metric to an insane degree but which aren't actually useful.
That has been the case for decades. Once the low-hanging fruit were all picked, algorithms research became yet another highly specialized field. If you are not a researcher in a closely related area, most research papers are not worth your time.
Related: https://news.ycombinator.com/item?id=31149038 (40 comments)
https://news.ycombinator.com/item?id=31675015 (72 comments)
2022
Where is the paper / code for this?
First link in "further information"
https://cacm.acm.org/research/almost-linear-time-algorithms-...
In 2030, this algorithm will be expected to optimally solve some leetcode interview question.
Maybe someone could clarify something for me here:
o(n) seems like a stronger statement to me than O(n), since all o(n) algorithms are O(n), but the reverse is not true.
Also if o(n) applies to all n, however small, whereas O(n) applies only when n -> inf,
(From the Wikipedia page example: 2n = O(n) but 2n != o(n))
Then doesn’t that means this algorithm should be applicable to even small n’s? Then it would be the opposite of a galactic algorithm, as someone above suggested, wouldn’t it?
Or am I missing something?
Little o is still an asymptotic statement: it doesn’t have to apply for small n. A definition of f(n) = o(g(n)) is something like
Or, in other words, for sufficiently large n, g grows faster than f.lim (n -> infinity) f(n)/g(n) = 0For instance, this function is o(n), because 1e1000/n goes to 0 as n grows.
(Pseudo-Python for a piecewise function that grows exponentially to 10**1000 at n = 1000 and then remains constant after that.)f(n) = 10**n if n < 1000 else 1e1000If the complexity of an algorithm is 3↑↑64*n^0.999, the algorithm is o(n) but can safely be said to be galactic.
* Ps, if memory serves me correct, 3↑↑64 is Graham's number.
damn you constant factors [shakes fist in the air]
The abstract just says the time is m^(1+o(1))... anyone know if a more specific bound is stated anywhere?
Note that this is a „small o“, so o(1) captures terms that „divided by 1“ go to zero as m to infinity.
English Wikipedia has an explanation, too: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...
It means that you can choose constants such that the algorithm is as close to O(m) as you'd like.
In other words, it's an algorithm scheme that allows you to get an algorithm running in time O(m^ɛ) for any ɛ>1.
Sorry, where's that stated? I'm pretty doubtful of that claim because if that's what they meant they would say that -- they'd say it was O(m^(1+ɛ)), that would be well-understood notation. But what they wrote is that it's O(m^(1+o(1))), which, read as written, means it's a single bound that they're just not being very specific about.
I'm not asking for help decoding the notation; I'm asking for if anyone knows what the more detailed bound is that O(m^(1+o(1))) is abstracting.
That's because even the ACM link is an abbreviation of the actual paper.
Preprint at https://arxiv.org/abs/2203.00671
(Pages 68-75 build up the full details of the bound, which looks something like Õ(mκ⁻²α⁻²ϵ⁻¹). There are enough details over the preceding dozens of pages that I can't tell at a glance exactly what all the variables stand for.)
Technically this captures any logarithmic factors, such as exp(O(log^(7/8) m log log m)) as presented on page 75).
That is the specific bound. The little o is a function that aproaches 0 as n approaches infinity, referred to as asymptotically negligible.
I know what the notation means. I'm wondering what the actual function is. Using little o is a way of abstracting that information away.
I could be wrong but I think many times the researchers don't care about the exact function. It could be something like 1/log(log(n)) .
Yes, I am very aware that many times they don't, but that doesn't mean they shouldn't!
Fortunately, in many cases, even when the detail is omitted from the headline theorem, they did in fact do the work and it is in fact stated lower down in the body of the paper; or in other cases they fail to state it but it can be easily assembled from a few parts. That's why I was asking.
But sometimes though it's a big complicated thing and they were just like, eh, let's not bother figuring out exactly what it is. To which I say, laziness! You're just making other people do a proof-mine later! You're doing this much, do the work to get a concrete bound, because you can do it better than later proof-miners can!
I won't say that in an ideally functioning mathematics proof-mining would never be necessary, that'd be like saying that in a well-written mathematics one would never need to refactor, but c'mon, mathematicians should at least do what they can to reduce the necessity of it.
I was hoping for some kind of evolutionary algorithm. Giving up optimality in exchange for being able to solve problem instances with billions of items would be worth it.
I don’t want to spam, but I’ve been using rome2rio website/app to find complex connections. They’re definitely not using this algorithm, but I’ve always been fascinated that you get complex results almost immediately. I don’t know how they do it, but for me it’s one of the most fascinating works on the internet. Great job. [I’m not affiliated with them in any way]
Rome2Rio seems to find an optimal route, and the problem discussed in this post is about finding an optimal flow.
Both are fascinating problems, but quite different. Finding shortest paths was typically solved with Dijkstra's algorithm [1], until someone discovered an amazing optimization scheme by precalculating some information that speeds up the search algorithm dramatically [2]. Thanks to this breakthrough, one can now interactively drag routes on Google Maps, for instance. And have Rome2Rio.
Note that there was not a step directly from Dijkstra to contraction hierarchies (CH); in particular, you could route using Highway hierarchies (HH) before CH came along. Both assume a fairly static network, though.
Oh yes, there have been many intermediate steps, it's a fascinating search in itself. I'd love to have a book detailing the history of shortest path algorithms. Let's hope Knuth has time to add it to TAOCP.
Can this be used to improve the Bitcoin Lightning Network?
My words.
Solving a problem for computational efficiency is pointless.
Wy
Take a look at AI neural networks where they blast computational resources.
May be
One day this might help.
Reply to myself
Appreciate this post. And get back to writing.
Appreciation
Out of so many other less interesting post, this post caught my attention and nowhere it spoke about how it works, most importantly why it is needed.
I'm not expert, saying out of experience