A new paper gives a much better algorithm for approximating max flow in undirected graphs. Paper is here. Article for general readers is here. Although the new algorithm is asymptotically better, it remains to be seen if it is substantially better in the practical range. However, this is an example of discovering a substantially more efficient algorithm where one might not have guessed that substantial improvements were possible.
A new paper gives a much better algorithm for approximating max flow in undirected graphs. Paper is here. Article for general readers is here. Although the new algorithm is asymptotically better, it remains to be seen if it is substantially better in the practical range. However, this is an example of discovering a substantially more efficient algorithm where one might not have guessed that substantial improvements were possible.