Thursday, January 31, 2013

Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem

 

Not long ago, a team of researchers from Stanford and McGill universities broke a 35-year record in computer science by an almost imperceptible margin — four hundredths of a trillionth of a trillionth of a trillionth of a trillionth of a percent, to be exact. The advance — made to that poster child for hard-to-solve computer science quandaries, the “traveling salesman” problem — was too minuscule to have any immediate practical significance, but it has breathed new life into the search for improved approximate solutions.

The traveling salesman problem asks: Given a collection of cities connected by highways, what is the shortest route that visits every city and returns to the starting place? The answer has practical applications to processes such as drilling holes in circuit boards, scheduling tasks on a computer and ordering features of a genome. 

For the rest of the story: http://www.wired.com/wiredscience/2013/01/traveling-salesman-problem/all/

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...