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

New algorithm can dramatically streamline solutions to the ‘max flow’ problem

web.mit.edu

Post reply on HN
Print view View original

21–30 of 46 posts

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#21

Post by tubbzor »

cliveowen wrote: post #17
bidev wrote: post #16

Just a thought that , could use of Drones for transportation make this problem less useful ? I admire solution presented here however just saying.

Optimizing the distribution of goods through a network of highways is just one of the, literally, hundreds of applications where this could (and probably will) be useful.

You are very correct. Max-flow/min-cut reduces to tons of other problems where this algorithm will be optimized.

Here's a nice little introduction I found with some reductions on the first couple slides: http://www.cs.princeton.edu/courses/archive/spr04/cos226/lec...

I just finished my algorithms undergrad class last semester; one of the questions on the final was 'you are a terrorist looking to cut off supplies to your enemy, which 3 nodes must you destroy to cut off the supply network?' And there was a complicated graph with probably 10 nodes and twice as many edges (very difficult to brute force in the allotted time), and we had to find the min-cut which would severe the flow. Some really cool problems reduce to max-flow.

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#22

Post by jplewicke »

murbard2 wrote: post #12

This could be quite useful for Ripple, which is basically solving a max-flow min-cost problem over a credit lines graph.

Ripple is actually a generalized network flow problem, in which the flow through an edge can be multiplied by an exchange rate when converting between currencies. As a result, regular network flow algorithms don't apply. There's also another issue with using a minimum cost criterion, since the costs are in different currencies and it's not clear how to put them on the same footing.

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#23

Post by mcintyre1994 »

tubbzor wrote: post #21
cliveowen wrote: post #17

Earlier quoted context omitted.

Optimizing the distribution of goods through a network of highways is just one of the, literally, hundreds of applications where this could (and probably will) be useful.

You are very correct. Max-flow/min-cut reduces to tons of other problems where this algorithm will be optimized. Here's a nice little introduction I found with some reductions on the first couple slides: http://www.cs.princeton.edu/courses/archive/spr04/cos226/lec... I just finished my algorithms undergrad class last semester; one of the questions on the final was 'you are a terrorist looking to cut off supplies to y…

Our lecturer told us that the problem was initially considered simultaneously by Russians trying to optimise the rail transport of stuff from USSR back to Russia and Americans trying to work out the cheapest way to destroy that network. Not sure if it's true, but it helps me think about the problem a lot.

Edit: I clicked the link, he used them exact slides. That set of slides comes up a lot, they're great.

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#24

Post by murbard2 »

jplewicke wrote: post #22
murbard2 wrote: post #12

This could be quite useful for Ripple, which is basically solving a max-flow min-cost problem over a credit lines graph.

Ripple is actually a generalized network flow problem, in which the flow through an edge can be multiplied by an exchange rate when converting between currencies. As a result, regular network flow algorithms don't apply. There's also another issue with using a minimum cost criterion, since the costs are in different currencies and it's not clear how to put them on the same footing.

If you make cost the log of the conversion rate plus the log of the %age fee, and treat each node as a distinct node for each currency, you do get max flow min cost.

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#25

Post by mcintyre1994 »

abc_lisper wrote: post #19

It looks like this means we can now redirect traffic on highways to avoid congestion. I know current gps' do this now. But in future, they could suggest different paths for different users, even though they are travelling to the same approximate destination.

That sort of thing seems like a real possibility for self-driving cars and drones too. Swarm navigation sounds like a really interesting area actually.

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#26

Post by ryanobjc »

Shish2k wrote: post #5

For those (like me) who clicked because algorithms are fun but don't know the max flow problem specifically: http://en.wikipedia.org/wiki/Maximum_flow_problem TL;DR: what's the fastest way to transport a large amount of data over a mesh of many small pipes As someone who knows little about this problem or the laws of physics, I wonder if it could be solved using physics -- set up a series of physical pipes, pump wate…

max-flow is used to model a large variety of supply-chain type problems.

a much faster variant - this is a big deal!

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#29

Post by DannyBee »

I'm always wary of these kinds of research papers because they are often not using comparative benchmarks sanely.

However, that said, there are all kinds of interesting max flow problems, so hopefully it pans out in practice. Heck, even some profile based compiler optimizations can be formulated as max-flow problems.

Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem

#30

Post by politician »

codehero wrote: post #10
Shish2k wrote: post #5

For those (like me) who clicked because algorithms are fun but don't know the max flow problem specifically: http://en.wikipedia.org/wiki/Maximum_flow_problem TL;DR: what's the fastest way to transport a large amount of data over a mesh of many small pipes As someone who knows little about this problem or the laws of physics, I wonder if it could be solved using physics -- set up a series of physical pipes, pump wate…

Network routing is directed flow; water flow is undirected, so backflow is possible. The dangers of analogy....

There are many queues in the devices along a route which are not unbounded. Back pressure is still an issue.
Post reply on HN