MIT researchers have a new framework for approximately solving
ow problems in capacitated, undirected graphs and apply it to provide asymptotically faster algorithms for the maximum s-t flow and maximum concurrent multicommodity flow problems.
For the first time there is an almost-linear-time construction of an O(mo(1))-competitive oblivious routing scheme. No previous such algorithm ran in time better than ( e mn). By reducing the running time to almost-linear, our work provides a powerful new primitive for constructing very fast
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.
Maxflow problems are like airline scheduling.
If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
Wang is a prolific business-oriented writer of emerging and disruptive technologies. He is known for insightful articles that combine business and technical analysis that catches the attention of the general public and is also useful for those in the industries. He is the sole author and writer of nextbigfuture.com
, the top online science blog. He is also involved in angel investing and raising funds for breakthrough technology startup companies.
He gave the recent keynote presentation at Monte Jade event with a talk entitled the Future for You. He gave an annual update on molecular nanotechnology at Singularity University on nanotechnology, gave a TEDX talk on energy, and advises USC ASTE 527 (advanced space projects program). He has been interviewed for radio, professional organizations. podcasts and corporate events. He was recently interviewed by the radio program Steel on Steel on satellites and high altitude balloons that will track all movement in many parts of the USA.
He fundraises for various high impact technology companies and has worked in computer technology, insurance, healthcare and with corporate finance.
He has substantial familiarity with a broad range of breakthrough technologies like age reversal and antiaging, quantum computers, artificial intelligence, ocean tech, agtech, nuclear fission, advanced nuclear fission, space propulsion, satellites, imaging, molecular nanotechnology, biotechnology, medicine, blockchain, crypto and many other areas.