BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/471
DTSTAMP:20230914T125925Z
SUMMARY:How to Run your Chores\, and Get to Dinner on Time
DESCRIPTION:Speaker: Anupam Gupta (Carnegie Mellon University\nDepartment o
f Computer Science\n7203 Gates Building\nPiitsburg\, PA 15213\nUnited Stat
es of America)\n\nAbstract: \nAbstract: In the orienteering problem\, we a
re given a metric space (the distances are supposed to represent travel ti
mes between the locations)\, a start vertex ("home") and a deadline B\, an
d 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. Howe
ver\, 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 c
an get the reward. Each such waiting time is drawn from a known probabilit
y distribution. What can we do then? In this talk\, we will discuss adapti
ve and non-adaptive approximation algorithms for this stochastic orienteer
ing problem (his is based on work with Ravi Krishnaswamy\, Viswanath Nagar
ajan\, and R. Ravi).\n
URL:https://www.tcs.tifr.res.in/web/events/471
DTSTART;TZID=Asia/Kolkata:20140306T143000
DTEND;TZID=Asia/Kolkata:20140306T153000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR