16 ms·
Researchers achieve ‘absurdly fast’ algorithm for network flow
- pjdkoch 4y agoHere's a talk they gave: https://www.youtube.com/watch?v=KsMtVthpkzI https://www.youtube.com/watch?v=KsMtVthpkzI
- coip 4y agoThanks for sharing this
- AtlasBarfed 4y agoIt ALSO does minimum cost? Is this academically published? Is this newer than the various links that date to 2010?
- fnordpiglet 4y agoThis is remarkable. We live in amazing times.
- thorncorona 4y ago> 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 https://arxiv.org/abs/2203.00671
- deleted 4y ago[deleted]
- titanomachy 4y agoI'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"?
- themonteray 4y agoo(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.
- pfdietz 4y agoOr, 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.
- account42 4y agoI 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.
- pvillano 4y ago(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"
- linhvn 4y agoPrevious HN discussion: https://news.ycombinator.com/item?id=31149038 https://news.ycombinator.com/item?id=31149038
- doctorhandshake 4y agoNot 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.
- antegamisou 4y agoI'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.
- paulpauper 4y agoi 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 .
- MattPalmer1086 4y agoI 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.
- doctorhandshake 4y agoYeah 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 4y ago[deleted]
- wenc 4y agoI 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.
- daenz 4y agoComing to a coding interview near you!
- deleted 4y ago[deleted]
- uejfiweun 4y agoYes, only those who can intuitively discover this algorithm are fit to write HTML and JS at this company.
- symfoniq 4y agoI skimmed the paper, and it makes more sense than a lot of SPAs.
- hinkley 4y agoTax laws make more sense than a lot of SPAs...
- chottocharaii 4y agolol, coding interviews are truly absurd
- huachimingo 4y agoI'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-beginners/ https://profoundphysics.com/lagrangian-mechanics-for-beginne... How you would translate from the discrete, relational approach to the continuous, analytic one?
- ericbarrett 4y agoSusskind seems to think that Kolmogorov complexity is deeply related to quantum gravity: https://m.youtube.com/watch?v=6OXdhV5BOcY https://m.youtube.com/watch?v=6OXdhV5BOcY
- enasterosophes 4y agoI 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 :)
- erosenbe0 4y agoFrom 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.
- ActionPlankton 4y agoKeywords: 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.
- DeathArrow 4y agoSo 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.
- ekkeke 4y agoIn 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.
- bringthesaas 4y agoYea 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.
- bainsfather 4y agoCan 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.
- amelius 4y agoIsn't the Quanta article supposed to be the 'friendly' overview?
- DIARRHEA_xd 4y agoIt'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".
- langsoul-com 4y agoHope someone makes a package for it.
- DeathArrow 4y agoReading 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.
- devnull3 4y agoNice! Now this would be expected algo from candidates in google/meta interviews, especially for senior IC roles. Update your leetcode answers folks.
- nothrowaways 4y agoLink to the paper https://arxiv.org/abs/2203.00671 https://arxiv.org/abs/2203.00671
- jl2718 4y agoIs 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.
- andersource 4y agoFrom 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.
- dchftcs 4y agoYears 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.
- amelius 4y agoLooking at the opening picture: is it allowed to fly a drone over busy traffic?
- roketridah 4y agoDepends 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.
- robertlagrant 4y agoGreat 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.
- cschmidt 4y agoI 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).
- benibela 4y agoAmazing 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?
- qubex 4y agoI 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.
- gauddasa 4y agoThe 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.
- nephanth 4y ago> 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.
- ligerzer0 4y agoAs 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