TITLE: Computing Everywhere: The Traveling Salesman Problem and Paris Fashion Week AUTHOR: Eugene Wallingford DATE: June 16, 2018 3:58 PM DESC: ----- BODY: I just read Pops, Michael Chabon's recent book of essays on fatherhood. The first essay, which originally appeared as an article in GQ, includes this parenthetical about his tour of Paris fashion week with his son:
-- a special mapping algorithm seemed to have been employed to ensure that every show was held as far as possible from its predecessor and its successor on the schedule --
My first thought was to approach this problem greedily: Start with the first show, then select a second show that is as far away as possible, then select a third show that is as far away as possible from that one, and so on, until all of the shows had been scheduled. But then I figured that a schedule so generated might seem laborious to travel at first, when there are plenty of faraway shows to choose from, but it might eventually start to seem pretty reasonable as the only shows left to schedule are relatively close. We can generate a more wholly sort of unsatisfactory schedule by maximizing the total travel time of the circuit. That's the Traveling Salesman Problem, inverted. Taking this approach, our algorithm is quite simple. We start with the usual nxn matrix d, where d[i,j] equals the distance between shows i and j. Then:
  1. Replace the distance between every two show locations d[i,j], with -(d[i,j]), its additive inverse.
  2. Call your favorite TSP solver with the new graph.
Easy! I leave implementation of the individual steps as an exercise for the reader. (By the way, Chabon's article is a sweet story about an already appreciative dad coming to appreciate his son even better. If you like that sort of thing, give it a read.) -----