31–40 of 46 posts
Also, are there a class of algorithms where the current practical state of the art differs greatly from the theoretical or how would I go about finding out the answer to this question? Much obliged.
I kind of thought a lot of these routing problems were worked out or known not to be work-out-able. Just shows what I know :/ * sigh
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations: http://arxiv.org/pdf/1304.2338v2.pdf
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…
Nobody uses brute-force computation to solve max-flow. The problem lies in P.
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.
EDIT: For an example, let's say the current best algorithm for some problem takes O(N^2), with a small constant (let's say 100 * N^2 operations). Then someone comes up with a O(N^1.9), but with a larger constant (let's say it takes 1,000,000 * N^1.9). The newer algorithm will practically be slower for any reasonably-sized input you can throw at it, even though it's a major theoretical breakthrough.
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…
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
http://www.americanscientist.org/issues/feature/the-soap-fil...
Earlier quoted context omitted.
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.
Could it be? http://arxiv.org/abs/1304.2338
Yes. Downloaded that too. Here is more: http://math.mit.edu/~kelner/publications.html I cant wait to see the C99 code for that! (maybe I should try that myself)
Earlier quoted context omitted.
Yes. Downloaded that too. Here is more: http://math.mit.edu/~kelner/publications.html I cant wait to see the C99 code for that! (maybe I should try that myself)
i'm kinda hoping to have some time to hack out a haskell implementation of the SDD solver next month (not sure if i'll have the time then, but I hope to)
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.
These papers improve time complexity, not actual running time. I'm not sure it ever makes sense to do comparative benchmarking, since you can't test on arbitrarily large inputs (which is what's important when looking at algorithm complexity). For smaller inputs (for example, N in the 1000-1 million range), constant factors impact running time significantly. To compensate, you'd have to run a benchmark of size 10^10,0…
And "these papers" often do care about running time and will say whether it is possible to implement the algorithm efficiently, if you're lucky they'll even have done an implementation and you can see at what dataset sizes they are faster in practice.
And even if it were slower in practice, research like this is very useful, because it helps gives other researchers inspiration, ever since someone thought of looking at these problems like electrical flow in 2010, there have been ever faster approximations for it, while others will find ways to implement the algorithm efficiently, just in case a naive implementation of the offered algorithm isn't efficient enough.
Dismissing such research without having found any actual extreme inefficiencies in the proposed algorithm is not an attitude suited to anyone who wants to see progress.
And finally, the actual speed increase in the past decades hasn't been from O(N^2) to O(N^1.9) but from O(VE^2) to O(VE), which obviously does have a real impact, and even with a non-realistic 10000 times bigger constant it would still be far faster in any graph with more 10000 edges. And graphs with billions of edges aren't unusual anymore.
Earlier quoted context omitted.
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.