It’s a seemingly simple scenario that has stumped great mathematicians for almost a century: Given a list of points on a map, what is the best way to determine the shortest possible route a traveler could take to visit each city on the list and make it back to the point of origin or another location?
This great puzzle is nicknamed “the traveling salesman problem,” but it could also be the “harried Tech undergrad problem.” What student hasn’t been faced with a laundry list of stuff to do and people to see on campus, and a limited amount of time to get everything done?
William Cook, Chandler Family Professor in the School of Industrial and Systems Engineering at Tech, dug deep into the maddening history of the problem in his book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, published in December by Princeton University Press.
To see his work in action, the Alumni Magazine drafted up a list of errands and tasked him with plotting out the optimal route.
Start: Morning class at the Couch building.
End: A well-earned nap in your North Avenue dorm.
Errands to run:
• Drop off a paper at your biology professor’s office in Cherry Emerson.
•
Return a book to the library.
•
Check your mailbox at the Student Center.
•
Swim a few laps at the CRC.
•
Swing by the Alumni House to join the Student Alumni Association.
•
Grab an empanada and a popsicle at the Farmer’s Market on Tech Walkway.
•
Pick up a new Tech sweatshirt and a coffee at the Tech Square Barnes & Noble.
•
Check out a friend’s photography on display at the Clough Commons gallery.
•
Study on the Tech Tower lawn for tomorrow’s big exam.
Here’s how Cook mapped it out (refer to the map above to see the route).
- CRC
- Student Center
- Tech Walkway
- Library
- Clough Commons
- Cherry Emerson
- Barnes & Noble
- Tech Tower lawn
- Alumni House
Twitter