7 ms·
Researchers develop the fastest possible flow algorithm
- squarerootof-1 2y agoWhere is the paper / code for this?
- styluss 2y agoFirst link in "further information" https://cacm.acm.org/research/almost-linear-time-algorithms-for-maximum-flow-and-minimum-cost-flow/ https://cacm.acm.org/research/almost-linear-time-algorithms-...
- elwell 2y agoIn 2030, this algorithm will be expected to optimally solve some leetcode interview question.
- c-smile 2y ago> Almost-Linear-Time Algorithm From O(mn) to O(m) ... thus excluding N (number of vertices) from computation ... Too good to be true?
- progbits 2y agoConstant factor so large it's going to be slower than existing (asymptotically worse) algorithms on any practical inputs. Still, a neat theoretical result.
- 8474_s 2y agoThe 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.
- Jabbles 2y agoMaybe, 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.
- Sniffnoy 2y agoThe abstract just says the time is m^(1+o(1))... anyone know if a more specific bound is stated anywhere?
- Zacharias030 2y agoNote that this is a „small o“, so o(1) captures terms that „divided by 1“ go to zero as m to infinity. https://de.m.wikipedia.org/wiki/Landau-Symbole https://de.m.wikipedia.org/wiki/Landau-Symbole
- yorwba 2y agoEnglish Wikipedia has an explanation, too: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...
- JohnKemeny 2y agoIt 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.
- Sniffnoy 2y agoSorry, 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.
- vitus 2y agoThat's because even the ACM link is an abbreviation of the actual paper. Preprint at https://arxiv.org/abs/2203.00671 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).
- deleted 2y ago[deleted]
- nabla9 2y agoThe 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-for-maximum-flow-and-minimum-cost-flow/ https://cacm.acm.org/research/almost-linear-time-algorithms-...
- aaron695 2y ago[dead]
- optimalsolver 2y agoSo it's another galactic algorithm? https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
- poincaredisk 2y agoI 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.
- FabHK 2y ago[flagged]
- nnoremap2 2y agoI mean nobody is stopping me from writing an exponential time algorithm.
- Dylan16807 2y ago
- JohnKemeny 2y agoRelated: https://news.ycombinator.com/item?id=31149038 https://news.ycombinator.com/item?id=31149038 (40 comments) https://news.ycombinator.com/item?id=31675015 https://news.ycombinator.com/item?id=31675015 (72 comments)
- nothrowaways 2y ago2022
- ziofill 2y agodamn you constant factors [shakes fist in the air]
- rowanG077 2y agoSometimes 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.
- jltsiren 2y agoThat 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.
- _f9cu 2y agoMy 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.
- _f9cu 2y agoI'm not expert, saying out of experience
- josefrichter 2y agoI 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]
- smokel 2y agoRome2Rio 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. [1] https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm [2] https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies
- Sesse__ 2y agoNote 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.
- smokel 2y agoOh 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.
- jpster 2y ago> 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?
- imtringued 2y agoI 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.
- ecstrema 2y agoMaybe 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?
- dbaupp 2y agoLittle 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 lim (n -> infinity) f(n)/g(n) = 0 Or, in other words, for sufficiently large n, g grows faster than f. For instance, this function is o(n), because 1e1000/n goes to 0 as n grows. f(n) = 10**n if n < 1000 else 1e1000 (Pseudo-Python for a piecewise function that grows exponentially to 10**1000 at n = 1000 and then remains constant after that.)
- JohnKemeny 2y agoIf 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.
- okintheory 2y agoInterestingly, 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. [1] https://arxiv.org/pdf/2303.00709 https://arxiv.org/pdf/2303.00709 [2] https://arxiv.org/abs/cs/0310051 https://arxiv.org/abs/cs/0310051
- I_am_tiberius 2y agoCan this be used to improve the Bitcoin Lightning Network?