"Traveling Salesman Problems Motivated by Robot Navigation"

number of packages. The robot should deliver packages in a timely
manner, with the more important packages getting priority over less
important ones. One classic model of such a scenario is the Traveling
Salesman Problem, in which we ask for the tour that visits all the sites
and whose length is as short as possible. However, a robot might break
down before visiting everything, for example, due to its battery running
out.

Such uncertainty about the future arises in many real-world planning
scenarios. Within the rich framework of Markov Decision Processes
(MDPs), the area which motivated this work, such uncertainty is often
handled by discounting the present value of rewards that will
be received in the distant future. Alternatively, one might ask for a
path that maximizes total reward value of sites visited subject to a
constraint that the total length is at most some given bound. This is
known as the Orienteering Problem.

In this talk, we will show that the above approaches are closely
related, and describe the first constant-factor approximation
algorithms for the Orienteering problem, as well as a new
problem that we call the Discounted-Reward TSP. Although the unrooted
Orienteering problem, has been known to be approximable using algorithms
for related problems such as k-TSP, ours is the first to approximate
the rooted question, solving a long-standing open problem.