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.
[ Parent
| on HN ]
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...