DIMACS Theoretical Computer Science Seminar

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

Speaker: Anupam Gupta, Carnegie Mellon University

Date: Wednesday, October 10, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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.

See: http://paul.rutgers.edu/~yixinxu/theory-fall12.html