Tourist Path Optimization Problem
We wish to study a variant of the Prize Collecting Traveling Salesmen Problem. Specifically given a set of nodes each with a time dependent reward function and a set edges each of which has a cost in time to travel return a path that maximizes the total reward given a total time and returns to the start. The Dual of minimizing the time required to achieve certain level of reward is also of interest. What is unique about this problem is that the reward for going to a node is dependent on the amount of time you spend at each node and thus the optimization must be done not only over which nodes to visit but also how long to stay at each node for. The goals for this project are to develop an Online or Approximation Algorithm to allow us to compute good solutions efficiently.

I am a senior studying computer science and math. I am looking forward to this project to leverage my experience in both of these fields to approach a basic problem with many higher level applications. Throughout the year I hope to gain insights into how to develop new algorithms and how to modify existing ones to solve new problems.