First improvement of fundamental algorithm in 10 years
1–10 of 42 posts
Re: First improvement of fundamental algorithm in 10 years
#2The article refers to the max flow problem. About all this article does is imply that the new method involves the adjacency matrix of the graph and provides little else in the way of details. A better article is needed, not this oversimplified press release.
Re: First improvement of fundamental algorithm in 10 years
#3The article refers to the max flow problem. About all this article does is imply that the new method involves the adjacency matrix of the graph and provides little else in the way of details. A better article is needed, not this oversimplified press release.
Kelner is set to give a talk about it tomorrow[1]. Anyone know if they create videos for these?
[1]: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...
Re: First improvement of fundamental algorithm in 10 years
#4Anyone have a link to the actual paper(s)?
Re: First improvement of fundamental algorithm in 10 years
#5from http://theory.csail.mit.edu/toc-seminars/ (can't find the actual paper...)
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
The maximum flow problem and its dual, the minimum s-t cut problem, are two of the most fundamental and extensively studied problems in Operations Research and Optimization. They have many direct applications and are also often used as subroutines in other algorithms.
In this talk, I'll describe a fundamentally new technique for approximating the maximum flow in capacitated, undirected graphs. I'll then use this technique to develop the asymptotically fastest-known algorithm for solving this problem. For graphs with n vertices and m edges, the algorithm computes epsilon-approximate maximum flows in time \tilde{O}(m^{4/3})poly(1/epsilon) and computes epsilon-approximate minimum s-t cuts in time \tilde{O}(m+n^{4/3})poly(1/epsilon).
We compute these flows by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.
This is joint work with Paul Christiano, Aleksander Madry, Daniel Spielman, and Shanghua Teng.
Re: First improvement of fundamental algorithm in 10 years
#6Anyone have a link to the actual paper(s)?
I looked around, but the only links I could find appear to be selected textbook chapters that describe old ways of doing it. Even Dr. Dobbs just reprinted the MIT press release. So far, the only useful link I can find is to the scheduled talk and someone already posted that.
If anyone can find anything more than this link, it would be interesting to me, too: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...
EDIT: Incidentally that page does tell us a bit more about the solution than the press release everyone is reprinting. Specifically, it says: "We compute these flows by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time."
Re: First improvement of fundamental algorithm in 10 years
#7The article refers to the max flow problem. About all this article does is imply that the new method involves the adjacency matrix of the graph and provides little else in the way of details. A better article is needed, not this oversimplified press release.
Kelner is set to give a talk about it tomorrow[1]. Anyone know if they create videos for these? [1]: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...
The method sounds very interesting, but the title seems to overstate the work a bit. This is an approximation algorithm, meaning that it's an improvement on an _approximate_variant_of_ a fundamental problem, right?
Re: First improvement of fundamental algorithm in 10 years
#8Very little info, but I'd argue that the parallel qualities of the new algorithm are at least of similar importance to the improvement in complexity.
Old speed: (N + L)^(3/2) New speed: (N + L)^(4/3). (n=nodes, l=links)
>For a network like the Internet, which has hundreds of billions of nodes, the new algorithm could solve the max-flow problem hundreds of times faster than its predecessor.
Granted, it's massively useful for Internet-scale calculations. But it's also massively useful that this is just operations on a matrix - throw the sucker at a video card, and watch it finish thousands of times faster on cheaper hardware.
edit: oh, and:
100,000,000^(3/2)) / 100,000,000^(4/3) ≈ 21.5
1,000,000,000^(3/2) / 1,000,000,000^(4/3) ≈ 31.6
1,000,000,000,000^(3/2) / 1,000,000,000,000^(4/3) ≈ 100
Re: First improvement of fundamental algorithm in 10 years
#9Their "represent it as a matrix" approach reminded me of this Richard Feynman story:
[...] Richard had completed his analysis of the behavior
of the router, and much to our surprise and amusement, he
presented his answer in the form of a set of partial
differential equations. To a physicist this may seem
natural, but to a computer designer, treating a set of
boolean circuits as a continuous, differentiable system is
a bit strange.
Feynman's router equations were in terms of variables
representing continuous quantities such as "the average
number of 1 bits in a message address." I was much more
accustomed to seeing analysis in terms of inductive proof
and case analysis than taking the derivative of "the
number of 1's" with respect to time.
Re: First improvement of fundamental algorithm in 10 years
#10Here's a good background paper by Spielman that seems to lay the foundation for the methods used:
http://www.cs.yale.edu/homes/spielman/PAPERS/icm10post.pdf
Although not the actual result itself. But looks like a really good read.