Imagine you are planning a road trip. To save time and gas, you want to choose the shortest route that goes through all the cities you want to visit. How do you figure out what path to take? One option is the brute force approach — measuring and comparing the lengths of every possible route to find the shortest one. However, the number of possible paths grows very quickly as you add more destinations. With five cities to visit there are 24 possible routes, but with 22 there are approximately 25 billion billion routes. An algorithm that checks every possible path would be too slow to be useful.
The goal is to find a general and efficient method for finding the shortest path through a set of points that goes through each point exactly once and returns to the starting point.
This problem is called the traveling salesperson problem, and it has captivated mathematicians and computer scientists for decades. The goal is to find a general and efficient method for finding the shortest path through a set of points that goes through each point exactly once and returns to the starting point.
The traveling salesperson problem has many varied applications, the most common of which involve transportation logistics such as bus and delivery routes. Planning effective delivery routes has large implications for the profits of companies such as Amazon, which awarded a $100,000 prize in June 2021 to the group that could provide the best machine learning model that learned from and predicted delivery routes taken by drivers. Methods for solving the traveling salesperson problem have also been used in genome sequencing and the production of circuit boards.
Solving the traveling salesperson problem would mean creating a polynomial-time algorithm, a computer algorithm whose execution time is modeled by a polynomial function. As the number of stops increases, the time taken by a polynomial-time algorithm would increase much more slowly than that of the brute force approach, which is an example of a factorial-time algorithm. To date, no polynomial-time algorithm that works for every possible set of points has been found. In fact, Richard Karp proved in 1972 that the traveling salesperson problem belongs to the NP-hard class of problems. This means that no efficient algorithm exists unless the conjecture P=NP is true. This conjecture asserts that problems whose solutions can be verified in polynomial time can also be solved in polynomial time. It is widely believed among computer scientists today that P=NP is false.
The focus of current research is using math to write algorithms that find an approximate solution: a path with a length within a certain percentage of the length of the shortest path. In 1976, Nicos Christofides wrote an algorithm that finds a route that is no more than 50% longer than the shortest route. Christofides’s algorithm is fairly simple. It first finds the shortest tree, a network without closed loops, that connects all of the points. In a closed loop all points must have an even number of branches, so to turn the tree into a loop the algorithm connects the points with an odd number of branches to each other in an optimal way. Computer scientists believed at the time that a more accurate algorithm would soon be developed, but that breakthrough did not come for another 44 years.
In 2010, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh began working together to beat Christofides’s record. Instead of choosing the shortest tree that connects all of the points, they created a collection of carefully chosen trees and chose a random tree from that set before using Christofides’s algorithm to turn the tree into a round trip. In July 2020, Oveis Gharan, Anna Karlin, and Nathan Klien published a paper proving that the new algorithm outperformed Christofides’s by 0.2 billionth of a trillionth of a trillionth of a percent. This improvement is incredibly small, but it breathed new life into the search for a more accurate algorithm because it showed that improving Christofides’s algorithm is possible.
When you’re planning your next road trip, you may never have a polynomial-time algorithm to find the shortest route, but researchers have come a long way at finding solutions to the traveling salesperson problem. These new understandings of the problem have profound implications: they shed light on related optimization problems and are useful for a wide array of applications.
This article was edited by Cat Kim and Ashley Schefler.