Computers are good at answering questions.
Whats 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, theyve got you covered.
My favorite hard problem is thetraveling salesperson problem.
I work on approximation algorithms as acomputer scientist.
It’s free, every week, in your inbox.
This is important for more than just planning routes.
You might say that these hard problems are all the same computational gremlin wearing different hats.
The best route is hard to find
The problem is usually stated as find the shortest route.
Do you think you could figure out the cheapest itinerary that visits them all?
Consider the sheer number of possible routes.
This is larger than the number of atoms in the universe.
This collection of dots and lines is the shortest traveling salesperson problem tour that passes through 1,000 points.
Its OK if a salesperson takes a route thats a few miles longer than it has to be.
This TSP tour is an efficient layout for circuits on a circuit board.
The Christofides-Serdyukov algorithm is quite simple, at least as algorithms go.
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.
However, this not a solution.
This algorithm runs quickly and always produces a solution thats at most 50% longer than the optimal one.
But its possible to prove something about the worst-case scenario.
The algorithm we analyzed is very similar to Christofides-Serdyukov.
We use this randomnessto show that we dont always get stuckwhere the previous algorithm did.
The question that theoreticians hope to answer is: How close can we get?
