Thursday, June 12, 2008
Combinatorial problems are one of the toughest nuts to crack in design automation and other applications that sift data. For instance, the number of Internet router path combinations for sending a message around the world is enormous. The shortest path is seldom chosen because there is no way to find the optimal distance among so many possibilities. Now, the developers of an algorithm called "Saucy" claim it can solve such problems quickly by finding symmetries among large swaths of possibilities. In the global Internet routing problem, Saucy found so many symmetries--10 with 83,687 zeros--that it could sort through and an find an optimum path in under a second. Saucy was described this week at the Design Automation Conference.
Posted by R. Colin Johnson at 7:54 AM