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. 1.3. There exists a constant-factor approximation algorithm to the optimal non-adaptive policy for stochastic orienteering. Note that if we could show an existential proof of a constant adaptivity gap (which we conjecture to be true), the above approximation for non-adaptive problems that we show immediately implies an O(1)-approximation algorithm for the adaptive problem too. Our second set of results are for a variant of the problem, one where both the rewards and the job sizes are random and correlated with each other. For this correlated problem, we show the following results: Theorem 1.4. There is a polynomial-time algorithm that outputs a non-adaptive solution for correlated stochastic orienteering, which is an O(log n log B)-approximation to the best adaptive solution. Moreover, the correlated problem is at least as hard as the orienteering-with-deadlines problem. Recall that we only know an O(log n) approximation for the orienteering-with-deadlines problem [BBCM04]. Our Techniques: Most of the previous adaptivity gaps have been shown by considering some linear programming relaxation that captures the optimal adaptive strategies, and then showing how to round a fractional LP solution to get a non-adaptive strategy. But since we do not know a good relaxation for even the deterministic orienteering problem, this approach seems difficult to take directly. So to show our adaptivity gap results, we are forced to argue directly about the optimal adaptive strategy: we use martingale arguments to show the existence of a path (a.k.a. non-adaptive strategy) within this tree which gives a large reward. We can then use algorithms for the non-adaptive settings, which are based on reductions to orienteering (with an additional knapsack constraint). Roadmap: The rest of the paper follows the outline above. We begin with some definitions in Section 2, and then define and give an algorithm for the knapsack orienteering problem which will be a crucial sub-routine in all our algorithms in Section 3. Next we motivate our non-adaptive algorithm by discussing a few straw-man solutions and the traps they fall into, in Section 4. We then state and prove our constant-factor non-adaptive algorithm in Section 5, which naturally leads us to our main result in Section 9, the proof of the O(log log B)-adaptivity gap for StocOrient. Finally, we present in Section 13 the poly-logarithmic approximation for the problem where the rewards and sizes are correlated with each other. For all these results we assume that we are not allowed to cancel jobs once we begin working on them: in Section 18 we show how to discharge this assumption. 2 Actually, one should really replace the stochastic job with a deterministic one of size E[min(S j , B − d(ρ, j))] and reward r j · Pr[S j + d(ρ, j) ≤ B], it is very easy to fool the algorithm otherwise.
Gupta et al. REF generalized the stochastic knapsack problem to the stochastic orienteering problem, where each stochastic item now resides on a vertex of a given metric, and we need to fit both the tour length and the item sizes inside our budget B. ey give an O(log log B)-approximation non-adaptive algorithm for this problem.
Approximation algorithms for stochastic orienteering
SODA
Computer Science