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.
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.
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.
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.
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.
> 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.
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?
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.
(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).
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.
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-...