3 ms·
Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem
- ColinWright 14y agoThis seems word-for-word identical to the submission here: http://news.ycombinator.com/item?id=5142480 http://news.ycombinator.com/item?id=5142480 Edit: I've checked - they are effectively identical. The comments there point out that this is for a restricted version of the TSP, one in which the edge weightings form a metric (and hence can't be negative). It's unclear to me if that version is NPC. The Wired.com article was also submitted 17 and 18 hours ago, with no discussion. I include the links here purely for completeness: http://news.ycombinator.com/item?id=5140429 http://news.ycombinator.com/item?id=5140429 http://news.ycombinator.com/item?id=5140792 http://news.ycombinator.com/item?id=5140792