How to Run your Chores, and Get to Dinner on Time

**Anupam Gupta**

**Monday, October 1, 2012**

4:00pm 5130 Upson Hall

__Abstract:__

In the orienteering problem, we are given a metric space (the
distances are supposed to represent travel times between the
locations), a start vertex ("home") and a deadline B, and want
to visit as many points as possible using a tour of length at
most B. We know constant-factor approximation algorithms for
this problem.

However, suppose it is not enough for us to visit the nodes:
upon reaching a location, we also have to wait for some time
at each location before we can get the reward. Each such waiting
time is drawn from a known probability distribution. What can
we do then? In this talk, we will discuss adaptive and non-adaptive
approximation algorithms for this stochastic orienteering problem.

This is based on work with Ravi Krishnaswamy, Viswanath Nagarajan,
and R.Ravi, which was presented at the SODA 2012 conference.