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

21–30 of 80 posts

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

#21

Post by themonteray »

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

o(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.

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

#22

Post by theemathas »

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

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

#23

Post by magnio »

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

No. Any constant is in O(1), but not in o(1). Specifically, f=O(g) means f is (eventually) at most Cg for a certain C, but f=o(g) means f is (eventually) at most Cg for all C.

A useful, albeit not really rigorous, way to think about this is O is like ≤, while o is like <.

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

#24

Post by paulpauper »

antegamisou wrote: post #11
doctorhandshake wrote: post #9

Not 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.

I'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.

i 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 .

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

#25

Post by ActionPlankton »

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?

Keywords: 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.

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

#27

Post by kkylin »

ActionPlankton wrote: post #25
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?

Keywords: 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 quad…

To expand on these themes, you may be interested in reading up on these & related topics:

Hamilton-Jacobi-Bellman equation: https://en.wikipedia.org/wiki/Hamilton%E2%80%93Jacobi%E2%80%...

Pontryagin maximum principle: https://en.wikipedia.org/wiki/Pontryagin%27s_maximum_princip...

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

#28

Post by [deleted] »

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?

[deleted]

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

#29

Post by wenc »

doctorhandshake wrote: post #9

Not 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.

I 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.

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

#30

Post by [deleted] »

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?

[deleted]
Post reply on HN