SFU Theory Seminar: Jason Schoeters

The talk starts with a short survey on a mathematical game known as Racetrack, in which a vehicle moves in discrete rounds and can slightly modify its movement vector every round. The goal is to minimize the amount of rounds needed to attain some destination. The survey includes complexity results, as well as algorithms and insights on the problem and on some variations of the problem. I will then introduce the Vector Traveling Salesman Problem (Vector TSP), in which one applies the Racetrack constraints to the visiting entity to effectively modelize speed, acceleration, and inertia forces in the well-known TSP. The difficulty lies in how to control these forces to visit the given set of locations in a minimum amount of rounds. We show this problem is NP-complete and explore a number of insights and algorithms related to this problem. In particular, the Racetrack constraints are powerful enough to possibly result in a different optimal visit order than the corresponding Euclidean TSP.