Tata Institute of Fundamental Research
How to Run your Chores, and Get to Dinner on Time
Seminar
Speaker:
Anupam Gupta (Carnegie Mellon University
Department of Computer Science
7203 Gates Building
Piitsburg, PA 15213
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Thursday, 6 Mar 2014, 14:30 to 15:30
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Anupam Gupta (Carnegie Mellon University Department of Computer Science 7203 Gates Building Piitsburg, PA 15213 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Thursday, 6 Mar 2014, 14:30 to 15:30 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
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).