Subscribe / Unsubscribe Enewsletters | Login | Register

Pencil Banner

MIT's new algorithm could solve thorny optimization problems

Joab Jackson | Jan. 9, 2014
A group of researchers at the Massachusetts Institute of Technology have devised a potentially more effective way of helping computers solve some of the toughest optimization problems they face.

With very complex networks, this approach can consume too much time and too many resources to work effectively. Today's problems often have millions or even billions of edges, Kelner pointed out.

The new algorithm tests all the paths, or edges, at once. The approach is much like electricity running through a circuit of parallel resistors, where the current will spread across all the possible paths at once. To further cut processing time, the algorithm can identify bottlenecks in a network, which max flow algorithms typically do not do.

While the formula could represent a breakthrough in solving optimization problems, much work still needs to be done getting it ready for production use in computers.

"The work we have published so far has focused on the theory, and it would be a fair amount of work to produce a good implementation that exactly follows it," Kelner wrote. The researchers will probably take another turn at making the algorithm simpler before attempting to implement it in a software library so it can be easily used by others.

 

Previous Page  1  2 

Sign up for Computerworld eNewsletters.