{"id":114740,"date":"2020-10-19T22:39:57","date_gmt":"2020-10-20T05:39:57","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2020\/10\/computer-scientists-break-the-traveling-salesperson-record"},"modified":"2020-10-19T22:39:57","modified_gmt":"2020-10-20T05:39:57","slug":"computer-scientists-break-the-traveling-salesperson-record","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2020\/10\/computer-scientists-break-the-traveling-salesperson-record","title":{"rendered":"Computer Scientists Break the \u2018Traveling Salesperson\u2019 Record"},"content":{"rendered":"<p><a class=\"aligncenter blog-photo\" href=\"https:\/\/lifeboat.com\/blog.images\/computer-scientists-break-the-traveling-salesperson-record2.jpg\"><\/a><\/p>\n<p>Now Karlin, Klein and Oveis Gharan have proved that an algorithm devised a decade ago beats Christofides\u2019 50 percent factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent. Yet this minuscule improvement breaks through both a theoretical logjam and a psychological one. Researchers hope that it will open the floodgates to further improvements.<\/p>\n<p>\u201cThis is a result I have wanted all my career,\u201d said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s.<\/p>\n<p>The traveling salesperson problem is one of a handful of foundational problems that theoretical computer scientists turn to again and again to test the limits of efficient computation. The new result \u201cis the first step towards showing that the frontiers of efficient computation are in fact better than what we thought,\u201d Williamson said.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Now Karlin, Klein and Oveis Gharan have proved that an algorithm devised a decade ago beats Christofides\u2019 50 percent factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent. Yet this minuscule improvement breaks through both a theoretical logjam and a psychological one. Researchers hope that [\u2026]<\/p>\n","protected":false},"author":396,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523,41],"tags":[],"class_list":["post-114740","post","type-post","status-publish","format-standard","hentry","category-computing","category-information-science"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/114740","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/396"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=114740"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/114740\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=114740"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=114740"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=114740"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}