Title: Approximation algorithms for stochastic orienteering
|Madison Van Dyk
|University of Waterloo
|MC 6029 or contact Rian Neogi for Zoom link
Abstract: This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed. We will discuss a non-adaptive approximation algorithm for this problem which was presented in a paper by Gupta, Krishnaswamy, Nagarajan, and Ravi. If time permits, we will examine its performance relative to the best adaptive policy.