2 ms·
I think the title is appropriate. The approximate solution is the interesting one, as the exact solution is believed to be intractable.
by schumitsch 16y ago
I think the title is appropriate. The approximate solution is the interesting one, as the exact solution is believed to be intractable.
- danger 16y agoI 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.3087 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.3...
- cdavidcash 16y agoThis 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.