Max flows in O(nm) time or better. jorlin.scripts.mit.edu/Max_flows_in_O…I'm thinking, wow, max flow is one of the major standard algorithms problems, and O(nm) time (n = number of vertices, m = number of edges) seems like a great clean bound. But there hasn't been much chatter about this result beyond Suresh's tweet.
— Suresh Venkat (@geomblog) August 31, 2012
Reading Orlin's paper gives some clues. The previous best bound due to King, Rao and Tarjan has a running time of O(nm logm/(n log n)n) = O(nm log n) just a logarithm off from O(nm). Orlin doesn't directly give an O(nm) algorithm, his takes time O(nm+m31/16log2n). It's the minimum of the running times of King-Rao-Tarjan and Orlin's algorithms that yields O(nm). Nor is O(nm) tight, Orlin also gives an algorithm with a running time of O(n2/log n) when m=O(n).
I don't mean to knock Orlin's work, he makes real progress on a classical algorithmic problem. But somehow I think of O(nm) as a magical bound when it is really just another bound. I'm just fooled by simplicity.