January 08, 2014

Classical computing and superalgorithms might do what we thought would need Quantum Computers

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
graph algorithms.

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

Congratulations! Now you can use SolidOpinion commenting system in all its magnificence! Click the link to get your password.

Форма для связи

Name

Email *

Message *