Publisher’s Note: Steve Manns’ essay was one of two essays that won the Benjamin Franklin Finkel Mathematics Essay Contest. The Northern Review congratulates Steve on this honor.
Consider the processes of drilling holes in circuit boards, scheduling tasks on a computer, ordering features of a genome, and arranging transportation for students to get to school. At first glance, there does not seem to be any connection. However, one of the most well-known problems in combinatorial optimization, that is, the Traveling Salesman Problem (TSP), relates these processes to one another quite convincingly. Essentially, the TSP poses the question: if a salesperson has a collection of n cities they wish to travel to as part of a business trip, what is the least costly route they can take to reach each city and return home? This problem is very practical; yet, to the contrary of what meets the eye, the solution is far from straightforward.
To illustrate the previous point, assume a salesperson wishes to visit four cities on their journey, not including their starting location. In this case, there are six different routes to be considered. Although it is likely not the most efficient method, this simple example can be solved using a brute force approach. In other words, one can compute the total distance traveled for each of the six routes and choose the one of minimum distance. When considering a more general case of the TSP, however, it is clear the brute force approach quickly becomes impractical. To that point, suppose the TSP problem is asymmetric, meaning the cost of traveling from location a to location b is not the same as the cost of traveling from b to a. Thus, a salesperson planning to travel to n different cities must choose between (n-1)! different routes. Now suppose the cost of traveling from location a to b is the same as going from b to a (i.e., the problem is symmetric). Even in this scenario, the salesperson must choose between (n-1)!/2 different routes. With the rapid growth of the factorial function, even the most advanced supercomputers cannot implement the brute force method when considering more than a modest number of cities. For example, an asymmetric TSP problem based on traveling to 15 different cities would require analyzing over 87 billion different paths.
Of course, with the capabilities of modern computers, mathematicians have been able to solve many problems that would otherwise be infeasible. While some complex problems can be solved using extremely fast algorithms, the only known algorithms for others are time consuming. As for the TSP, it is known to be “NP-hard,” which means it is unlikely a polynomial time solution exists. Accordingly, despite this problem having been contemplated by mathematicians since 1832, no one has been able to create an algorithm capable of solving any given TSP. Nonetheless, since the computer scientist Richard Karp from the University of California, Berkeley was able to show the TSP is NP-hard, there has been a tremendous effort to develop an algorithm capable of finding approximate solutions to the problem.
When evaluating approximation algorithms, there are two main ways to measure performance. First, one can base the evaluation on how far off the approximation is in the worst case. Secondly, one can focus on the performance of the algorithm in an average case problem. In light of the first evaluation technique, in 1976, Nicos Christofides developed an approximation algorithm guaranteed to produce a route no more than 50 percent longer than the optimal solution. While to some this may not seem to be an overly impressive accomplishment, Christofides’ algorithm stood untouched for decades.
Finally, in 2011, researchers at Stanford and McGill universities were able to develop an algorithm that ever so slightly improved on the mark reached by Christofides. It took over 35 years, but the newly developed algorithm outperformed the competition by a margin of “four hundredths of a trillionth of a trillionth of a trillionth of a trillionth of a percent.” Further improvements have been made since this time, and the current record stands at no more than 40 percent longer than the optimal route.
Keeping in mind how long Christofides’ algorithm maintained the title of the top performing approximation algorithm for the TSP, it is worth examining this approach in greater detail. Intuitively, it seems reasonable for the salesperson to begin their trip by traveling along the least costly path to a new city. Then, continuing with this strategy, the salesperson would move to another new city along the cheapest path. This strategy is known as a greedy algorithm and is based on making locally optimal decisions. Likewise, Christofides’ algorithm begins by finding a minimum spanning tree – a collection of branches connecting the cities with no cycles – using greedy algorithms. Despite the apparent intuitiveness of greedy algorithms, this will not produce an optimal solution. In fact, on account of the round-trip path produced by minimum spanning trees typically requiring retracing of steps, the result can be up to twice as long as the optimal solution. Nonetheless, the minimum spanning tree provides a necessary starting point, and Christofides showed a careful trimming of the minimum spanning tree produced results no worse than 50 percent longer than the shortest route.
Now, to return to the remark made in the introduction, to the average eye there may be no connection between the processes of drilling holes in circuit boards, scheduling tasks on a computer, ordering features of a genome, and arranging transportation for students to get to school. Be that as it may, the reader is left to contemplate the words of French mathematician and physicist, Joseph Fourier: “Mathematics compares the most diverse phenomena and discovers the secret analogies that unite them”. In the case of the TSP, the mathematician has leveraged their use of abstraction to develop an algorithm with real-world applications. While there are differences, the processes mentioned above all involve structuring tasks. Rather than blindly hoping for the best, these tasks are completed with mathematical precision thanks to the TSP. Thus, as proposed by Fourier and illustrated here, mathematics connects the seemingly unrelated.