{"id":25011,"date":"2021-04-11T22:58:00","date_gmt":"2021-04-11T22:58:00","guid":{"rendered":"https:\/\/www.lifeandnews.com\/articles\/?p=25011"},"modified":"2021-04-12T01:00:12","modified_gmt":"2021-04-12T01:00:12","slug":"planning-the-best-route-with-multiple-destinations-is-hard-even-for-supercomputers-a-new-approach-breaks-a-barrier-thats-stood-for-nearly-half-a-century","status":"publish","type":"post","link":"https:\/\/www.lifeandnews.com\/articles\/planning-the-best-route-with-multiple-destinations-is-hard-even-for-supercomputers-a-new-approach-breaks-a-barrier-thats-stood-for-nearly-half-a-century\/","title":{"rendered":"Planning the best route with multiple destinations is hard even for supercomputers \u2013 a new approach breaks a barrier that’s stood for nearly half a century"},"content":{"rendered":"\n

Nathan Klein<\/a>, University of Washington<\/a><\/em><\/p>\n\n\n\n

Computers are good at answering questions. What\u2019s the shortest route from my house to Area 51? Is 8,675,309 a prime number? How many teaspoons in a tablespoon? For questions like these, they\u2019ve got you covered.<\/p>\n\n\n\n

There are certain innocent-sounding questions, though, that computer scientists believe computers will never be able to answer \u2013 at least not within our lifetimes. These problems are the subject of the P versus NP question<\/a>, which asks whether problems whose solutions can be checked quickly can also be solved quickly. P versus NP is such a fundamental question that either designing a fast algorithm for one of these hard problems or proving you can\u2019t would net you a cool million dollars<\/a> in prize money.<\/p>\n\n\n\n

My favorite hard problem is the traveling salesperson problem<\/a>. Given a collection of cities, it asks: What is the most efficient route that visits all of them and returns to the starting city? To come up with practical answers in the real world, computer scientists use approximation algorithms, methods that don\u2019t solve these problems exactly but get close enough to be helpful. Until now, the best of these algorithms, developed in 1976, guaranteed that its answers would be no worse than 50% off from the best answer.<\/p>\n\n\n\n

I work on approximation algorithms as a computer scientist<\/a>. My collaborators Anna Karlin and Shayan Oveis Gharan and I have found a way to beat that 50% mark, though just barely. We were able to prove that a specific approximation algorithm puts a crack in this long-standing barrier, a finding that opens the way for more substantial improvements.<\/p>\n\n\n\n

This is important for more than just planning routes. Any of these hard problems can be encoded in the traveling salesperson problem, and vice versa: Solve one and you\u2019ve solved them all. You might say that these hard problems are all the same computational gremlin wearing different hats.<\/p>\n\n\n\n

The best route is hard to find<\/h2>\n\n\n\n

The problem is usually stated as \u201cfind the shortest route.\u201d However, the most efficient solution can be based on a variety of quantities in the real world, such as time and cost, as well as distance.<\/p>\n\n\n\n

To get a sense of why this problem is difficult, imagine the following situation: Someone gives you a list of 100 cities and the cost of plane, train and bus tickets between each pair of them. Do you think you could figure out the cheapest itinerary that visits them all?<\/p>\n\n\n\n

Consider the sheer number of possible routes. If you have 100 cities you want to visit, the number of possible orders in which to visit them is 100 factorial, meaning 100 \u00d7 99 \u00d7 98 x \u2026 \u00d7 1. This is larger than the number of atoms in the universe.<\/p>\n\n\n\n

\"A<\/a>
This collection of dots and lines is the shortest traveling salesperson problem tour that passes through 1,000 points. William Cook et al.<\/a>, CC BY-ND<\/a><\/figcaption><\/figure>\n\n\n\n

Going with good enough<\/h2>\n\n\n\n

Unfortunately, the fact that these problems are difficult does not stop them from coming up in the real world. Besides finding routes for traveling salespeople (or, these days, delivery trucks), the traveling salesperson problem has applications in many areas, from mapping genomes<\/a> to designing circuit boards<\/a>.<\/p>\n\n\n\n

To solve real-world instances of this problem, practitioners do what humans have always done: Get solutions that might not be optimal but are good enough. It\u2019s OK if a salesperson takes a route that\u2019s a few miles longer than it has to be. No one cares too much if a circuit board takes a fraction of a second longer to manufacture or an Uber takes a few minutes longer to carry its passengers home.<\/p>\n\n\n\n

Computer scientists have embraced \u201cgood enough\u201d and for the past 50 years or so have been working on so-called approximation algorithms. These are procedures that run quickly and produce solutions that might not be optimal but are provably close to the best possible solution.<\/p>\n\n\n\n

\"A<\/a>
This TSP tour is an efficient layout for circuits on a circuit board. William Cook et al.<\/a>, CC BY-ND<\/a><\/figcaption><\/figure>\n\n\n\n

The long-reigning champ of approximation<\/h2>\n\n\n\n

One of the first and most famous approximation algorithms is for the traveling salesperson problem and is known as the Christofides-Serdyukov algorithm<\/a>. It was designed in the 1970s by Nicos Christofides and, independently, by a Soviet mathematician named Anatoliy Serdyukov whose work was not widely known until recently.<\/p>\n\n\n\n

The Christofides-Serdyukov algorithm is quite simple, at least as algorithms go. You can think of a traveling salesperson problem as a network in which each city is a node and each path between pairs of cities is an edge. Each edge is assigned a cost, for example the traveling time between the two cities. The algorithm first selects the cheapest set of edges that connect all the cities.<\/p>\n\n\n\n

This, it turns out, is easy to do: You just keep adding the cheapest edge that connects a new city. However, this not a solution. After connecting all the cities, some might have an odd number of edges coming out of them, which doesn\u2019t make sense: Every time you enter a city with an edge, there should be a complementary edge you use to leave it. So the algorithm then adds the cheapest collection of edges that makes every city have an even number of edges and then uses this to produce a tour of the cities.<\/p>\n\n\n\n

This algorithm runs quickly and always produces a solution that\u2019s at most 50% longer than the optimal one. So, if it produces a tour of 150 miles, it means that the best tour is no shorter than 100 miles.<\/p>\n\n\n\n

Of course, there\u2019s no way to know exactly how close to optimal an approximation algorithm gets for a particular example without actually knowing the optimal solution \u2013 and once you know the optimal solution there\u2019s no need for the approximation algorithm! But it\u2019s possible to prove something about the worst-case scenario. For example, the Christofides-Serdyukov algorithm guarantees that it produces a tour that is at most 1.5 times the length of the shortest collection of edges connecting all the cities – and, therefore, at most 1.5 times the length of the optimal tour.<\/p>\n\n\n\n

A really small improvement that\u2019s a big deal<\/h2>\n\n\n\n

Since the discovery of this algorithm in 1976, computer scientists had been unable to improve upon it at all. However, last summer my collaborators and I proved that a particular algorithm will, on average, produce a tour that is less than 49.99999% away from the optimal solution<\/a>. I\u2019m too ashamed to write out the the true number of 9s (there are a lot), but this nevertheless breaks the longstanding barrier of 50%.<\/p>\n\n\n\n

The algorithm we analyzed is very similar to Christofides-Serdyukov. The only difference is that in the first step it picks a random collection of edges that connects all the cities and, on average, looks like a traveling salesperson problem tour. We use this randomness to show that we don\u2019t always get stuck<\/a> where the previous algorithm did.<\/p>\n\n\n\n

[Deep knowledge, daily.<\/em> Sign up for The Conversation\u2019s newsletter<\/a>.]<\/p>\n\n\n\n

While our progress is small, we hope that other researchers will be inspired to take another look at this problem and make further progress. Often in our field, thresholds like 50% stand for a long time, and after the first blow they fall more quickly. One of our big hopes is that the understanding we gained about the traveling salesperson problem while proving this result will help spur progress.<\/p>\n\n\n\n

Getting closer to perfect<\/h2>\n\n\n\n

There is another reason to be optimistic that we will see more progress within the next few years: We think the algorithm we analyzed<\/a>, which was devised in 2010, may be much better than we were able to prove. Unlike Christofides\u2019 algorithm, which can be shown to have a hard limit of 50%, we suspect this algorithm may be as good as 33%.<\/p>\n\n\n\n

Indeed, experimental results<\/a> that compare the approximation algorithm to known optimal solutions suggest that the algorithm is quite good in practice, often returning a tour within a few percent of optimal.<\/p>\n\n\n\n

The current theoretical limit is around 1%<\/a> \u2013 meaning that (unless P=NP) there is no algorithm that will be able to get within 1% of optimal. The question that theoreticians hope to answer is: How close can we get?<\/p>\n\n\n\n

Nathan Klein<\/a>, PhD Student in Computer Science, University of Washington<\/a><\/em><\/p>\n\n\n\n

This article is republished from The Conversation<\/a> under a Creative Commons license. Read the original article<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Nathan Klein, University of Washington Computers are good at answering questions. What\u2019s the shortest route from my house to Area 51? Is 8,675,309 a prime number? How many teaspoons in a tablespoon? For questions like these, they\u2019ve got you covered. There are certain innocent-sounding questions, though, that computer scientists believe computers will never be able […]<\/p>\n","protected":false},"author":44,"featured_media":25012,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3410],"tags":[2341,9745,8832,665],"_links":{"self":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/25011"}],"collection":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/users\/44"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/comments?post=25011"}],"version-history":[{"count":2,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/25011\/revisions"}],"predecessor-version":[{"id":25024,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/posts\/25011\/revisions\/25024"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/media\/25012"}],"wp:attachment":[{"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/media?parent=25011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/categories?post=25011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lifeandnews.com\/articles\/wp-json\/wp\/v2\/tags?post=25011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}