News for hackers. Stuff that matters.
Re:First improvement of fundamental algorithm in 10 years by T_S_ on Monday September 27, 2010 @03:52PM (#1733082)
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.
Re:First improvement of fundamental algorithm in 10 years by superjared on Monday September 27, 2010 @04:06PM (#1733162)
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 by danger on Monday September 27, 2010 @04:30PM (#1733273)
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 by btilly on Monday September 27, 2010 @06:00PM (#1733648)
If you're able to find a rapidly converging sequence of approximations, then in finite time you can approximate arbitrarily well. Given the realities of finite numerical precision, this can be exactly as useful as an exact solution.

We'll know more tomorrow.

Re:First improvement of fundamental algorithm in 10 years by cdavidcash on Monday September 27, 2010 @06:46PM (#1733810)
Sadly, "finite time" is not what we need - they are looking for approximations that will be much rougher than the imprecision of finite numerical precision, and they want the approximation algorithm to have a good provable run time.

In general, taking theoretical approximation algorithms and shrinking the approximation factor to below some threshold where you "tell the difference" is a dead end. For instance, this algorithm's running time has a poly^{1/\epsilon} factor, so you pay a huge cost for it. It is better to think \epsilon = 1/3 or so.

Re:First improvement of fundamental algorithm in 10 years by Confusion on Tuesday September 28, 2010 @02:24AM (#1734774)
Is there necessarily a difference? Some fundamental problems, including such simple things as the physical 3-body problem, don't have analytical solutions. That doesn't mean that approximate solutions solve an approximate problem. Algorithms can be designed to give an approximation to the optimal solution of the problem, which is known to be achievable only through ultimately numerical methods.

I don't know whether that is the case here: it is possible that they solve a different problem from the fundamental problem. However, even in that case: if the transformations made to turn the fundamental problem into a more tractable problem are generally applicable, then is there really a difference between solving the fundamental problem and solving the transformed problem?

Re:First improvement of fundamental algorithm in 10 years by schumitsch on Monday September 27, 2010 @06:00PM (#1733651)
I think the title is appropriate. The approximate solution is the interesting one, as the exact solution is believed to be intractable.
Re:First improvement of fundamental algorithm in 10 years by cdavidcash on Monday September 27, 2010 @06:51PM (#1733824)
This is absolutely not true. The wikipedia page for the max flow problem lists several (slower) poly-time algorithms for solving exact max flow. Most theory-101 classes cover at least Ford-Fulkerson.
Re:First improvement of fundamental algorithm in 10 years by danger on Monday September 27, 2010 @06:41PM (#1733797)
I don't think that's true. See, for example, Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (Karger-Levine, 1997): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.3...
Re:First improvement of fundamental algorithm in 10 years by sspencer on Monday September 27, 2010 @05:14PM (#1733451)
Any MIT people know if this is open to the public? Might be worth leaving work a bit early to listen to that talk.
Re:First improvement of fundamental algorithm in 10 years by woodrow on Monday September 27, 2010 @05:34PM (#1733538)
The email note and notice in the elevator says "THEORY COLLOQUIUM: Open to the Public".
Re:First improvement of fundamental algorithm in 10 years by cageface on Monday September 27, 2010 @05:30PM (#1733521)
Adjacency matrices are taught in undergraduate linear algebra classes. This article makes it sound like they invented them.
Re:First improvement of fundamental algorithm in 10 years by adw on Tuesday September 28, 2010 @08:40AM (#1735460)
They're taught in secondary schools in Scotland. (Or at least they were when I did CSYS Maths (Pure), now Advanced Higher...)
Re:First improvement of fundamental algorithm in 10 years by askar_yu on Monday September 27, 2010 @10:03PM (#1734302)
yes, but the article tries to explain the achieved work to people unfamiliar with Graph Theory or CS; thus in very simple terms and with analogies, they even define what a graph is before proceeding... I guess that's what it meant to be, short and simple press release with a (I'm assuming) follow up with the algorithm itself.