11–20 of 42 posts
Earlier quoted context omitted.
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?
The 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 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.
Earlier quoted context omitted.
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...
Any MIT people know if this is open to the public? Might be worth leaving work a bit early to listen to that talk.
I'm confused at how they claim O(m^{4/3}) (m is the number of edges) when even initializing an explicit n by n matrix is O(n^2), unless they assume that the graph isn't sparse (m>=k*n^1.5).
Or perhaps the matrix is sparsely represented.
Earlier quoted context omitted.
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?
We'll know more tomorrow.
Earlier quoted context omitted.
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?
Very 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 us…
(I have a CS degree, but I'm a circuit designer, so it's been a while since I've thought seriously about problems like this and I'm clearly not in touch with the state of the art. This question isn't snark, it's really a question.)