New algorithm can dramatically streamline solutions to the ‘max flow’ problem
1–10 of 46 posts
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#2This sounds really cool. Are there any links to the paper / presentation anywhere? I would love to learn more.
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#3Could it be?
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#4This sounds really cool. Are there any links to the paper / presentation anywhere? I would love to learn more.
Kelner's web site has the link (and confirms that it corresponds to what will be discussed at the ACM-SIAM symposium):
http://math.mit.edu/~kelner/publications.html
http://math.mit.edu/~kelner/Publications/Docs/1304.2338v2.pd...
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#5For 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 water from A to B, measure the flow at each point? If that would work, how complicated would the mesh need to be that solving it with physics is faster than brute-force computation?
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#6The abstract talks about ϵ-approximation for m edges in O(m^(1+o(1))ϵ^−2). If this algorithm is practical that would be quite a speed up!
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#7For 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…
Some people, when confronted with a problem, think "I know, I'll use a physical model." Now they have two problems.
(The new problem is dealing with fluid dynamics.)
Water-based computation has already been done of course: http://en.wikipedia.org/wiki/MONIAC_Computer
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#8For 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…
Some people, when confronted with a problem, think "I know, I'll use a physical model." Now they have two problems. (The new problem is dealing with fluid dynamics.) Water-based computation has already been done of course: http://en.wikipedia.org/wiki/MONIAC_Computer
[deleted]
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#9For 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…
This would be an example of an analogue simulation. You first need to prove that the behavior of the physical analogue is also a solution to the original problem. The classic example is solving Poisson's equation, which gives (among other things) the electric field in a space containing charges, by measuring the deformation of an elastic sheet.
Re: New algorithm can dramatically streamline solutions to the ‘max flow’ problem
#10For 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....