News for hackers. Stuff that matters.

A comment on New algorithm can dramatically streamline solutions to the ‘max flow’ problem. Parent comment

Re:New algorithm can dramatically streamline solutions to th... by mcintyre1994 on Tuesday January 07, 2014 @03:25PM (#7019659)
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.

[ Parent | on HN ]
Re:New algorithm can dramatically streamline solutions to th... by tubbzor on Wednesday January 08, 2014 @08:56AM (#7023426)
You are right! Edmonds-karp was developed (really just a modified Ford-Faulkerson approach with a BFS as opposed to a random augmenting path...but we'll give it to him), yielding an O(ve^2) algorithm. A russian (soviet) mathematician named Dinic nearly simultaneously, and independently, developed an O(ev^2) algorithm which we can see beats Edmonds-karp as edge density grows.
[ Parent | on HN ]