Combinatorial Optimization Reading Group - Madison Van Dyk

Friday, November 18, 2022 12:00 pm - 12:00 pm EST

Title: Approximation algorithms for stochastic orienteering  

Speaker: Madison Van Dyk
Affiliation: University of Waterloo
Location: 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.