TY - GEN

T1 - Approximation algorithms for stochastic orienteering

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

AU - Nagarajan, Viswanath

AU - Ravi, R.

PY - 2012

Y1 - 2012

N2 - In the Stochastic Orienteering problem, we are given a metric, where each node also has a job located there with some deterministic reward and a random size. (Think of the jobs as being chores one needs to run, and the sizes as the amount of time it takes to do the chore.) The goal is to adaptively decide which nodes to visit to maximize total expected reward, subject to the constraint that the total distance traveled plus the total size of jobs processed is at most a given budget of B. (I.e., we get reward for all those chores we finish by the end of the day). The (random) size of a job is not known until it is completely processed. Hence the problem combines aspects of both the stochastic knapsack problem with uncertain item sizes and the deterministic orienteering problem of using a limited travel time to maximize gathered rewards located at nodes. In this paper, we present a constant-factor approximation algorithm for the best non-adaptive policy for the Stochastic Orienteering problem. We also show a small adaptivity gap - i.e., the existence of a non-adaptive policy whose reward is at least an Ω(1/log log B) fraction of the optimal expected reward - and hence we also get an O(log log B)-approximation algorithm for the adaptive problem. Finally we address the case when the node rewards are also random and could be correlated with the waiting time, and give a non-adaptive policy which is an O(log n log B)-approximation to the best adaptive policy on n-node metrics with budget B.

AB - In the Stochastic Orienteering problem, we are given a metric, where each node also has a job located there with some deterministic reward and a random size. (Think of the jobs as being chores one needs to run, and the sizes as the amount of time it takes to do the chore.) The goal is to adaptively decide which nodes to visit to maximize total expected reward, subject to the constraint that the total distance traveled plus the total size of jobs processed is at most a given budget of B. (I.e., we get reward for all those chores we finish by the end of the day). The (random) size of a job is not known until it is completely processed. Hence the problem combines aspects of both the stochastic knapsack problem with uncertain item sizes and the deterministic orienteering problem of using a limited travel time to maximize gathered rewards located at nodes. In this paper, we present a constant-factor approximation algorithm for the best non-adaptive policy for the Stochastic Orienteering problem. We also show a small adaptivity gap - i.e., the existence of a non-adaptive policy whose reward is at least an Ω(1/log log B) fraction of the optimal expected reward - and hence we also get an O(log log B)-approximation algorithm for the adaptive problem. Finally we address the case when the node rewards are also random and could be correlated with the waiting time, and give a non-adaptive policy which is an O(log n log B)-approximation to the best adaptive policy on n-node metrics with budget B.

UR - http://www.scopus.com/inward/record.url?scp=84860189702&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860189702&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.121

DO - 10.1137/1.9781611973099.121

M3 - Conference contribution

AN - SCOPUS:84860189702

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1522

EP - 1538

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -