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


Anupam Gupta


Carnegie Mellon University
Department of Computer Science
7203 Gates Building
Piitsburg, PA 15213
United States of America


Thursday, 6 March 2014, 14:30 to 15:30



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 (his is based on work with Ravi Krishnaswamy, Viswanath Nagarajan, and R. Ravi).