Combinatorial Optimization Reading Group - Madison Van Dyk

Title: Approximation algorithms for stochastic orienteering  

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.