Title: On the Adaptivity Gap of Stochastic Orienteering
| Speaker: | Paul Lawrence |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 or contact Rian Neogi for the Zoom link |
Abstract: This talk highlights the stochastic orienteering problem, in which we are given a budget B and a graph G=(V,E) with edge distances d(u,v) and a starting vertex x. Each vertex v represents a job with a deterministic reward and a random processing time, drawn from a known distribution. The objective is to compute a path originating at x that maximizes expected reward among processed jobs, subject to the total distance traveled plus processing times not exceeding our budget. We will discuss the proof of a lower bound on the adaptivity gap of this problem, first on directed graphs and then on undirected graphs. Given time, we will mention additional results by the authors on the correlated stochastic orienteering problem.