Joint work with Avrim Blum and Shuchi Chawla (CMU) And David Karger and Maria Minkoff (MIT) And Terran Lane (University of New Mexico)
Consider a robot which delivers various packages. The robot needs to visit a series of locations, and the quality of the path selected is determined by the timeliness of the deliveries. We can assume that the robot recieves a reward for each package delivered, where the reward is determined by the package identity and the delivery time. Our goal is to find a path which maximizes the total reward.
In this talk, we consider two different functions relating reward to time. In the Orienteering problem, the rewards are fixed until a specified time, at which point all rewards drop to zero. This is the problem of maximizing the number of destinations visited before a specific deadline. In the Discounting problem, the reward decays exponentially with time. This model is frequently considered in the realm of Markov decision processes. For each of these two functions, we describe the first constant approximation algorithms.