The Revolution in Graph Theoretic Optimization Problems
Gary Lee Miller · 2015
Over the last several years there have been major breakthroughs in the design of approximation algorithms for such classic problems as finding the maximum flow in a graph. Maximum flow for undirected graphs can now be approximately solved in almost linear time. This result by researchers at Berkeley and MIT, I claim, is only the beginning of a new era in efficient algorithm design.