Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Researchers achieve ‘absurdly fast’ algorithm for network flow

quantamagazine.org

Post reply on HN
Print view View original

41–50 of 80 posts

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#41

Post by enasterosophes »

ericbarrett wrote: post #17
huachimingo wrote: post #16

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?

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 :)

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#42

Post by bainsfather »

DeathArrow wrote: post #31

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.

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.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#44

Post by aliceryhl »

titanomachy wrote: post #20
thorncorona wrote: post #4

> 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…

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"?

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

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#46

Post by tromp »

titanomachy wrote: post #20
thorncorona wrote: post #4

> 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…

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"?

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.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#47

Post by jl2718 »

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.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#48

Post by andersource »

jl2718 wrote: post #47

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 opinio…

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.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#49

Post by Jweb_Guru »

aliceryhl wrote: post #44
titanomachy wrote: post #20

Earlier quoted context omitted.

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"?

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!

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#50

Post by [deleted] »

im3w1l wrote: post #34
theemathas wrote: post #22

Earlier quoted context omitted.

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

I'm trying to come up with an example to check my understanding. n (log n)^k for some constant k would qualify right?

[deleted]
Post reply on HN