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...
[1]: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...