Combinatorial Optimization Reading Group - Paul Lawrence

Friday, October 7, 2022 12:00 pm - 12:00 pm EDT (GMT -04:00)

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.