TITLE: Approximation Algorithms for Stochastic Orienteering

SPEAKER: Viswanath Nagarajan

ABSTRACT:

Adaptive optimization deals with optimization problems having stochastic input, where a solution involves multiple stages of decisions, each of which reveals additional information about the realized input. We introduce and study a stochastic version of the orienteering problem in this setting. The deterministic orienteering problem is an extensively studied vehicle routing problem with many applications. Given a set of locations with associated rewards, distance bound B and a designated depot, the objective in orienteering is to find a path of length at most B originating from the depot that maximizes the total reward. In the stochastic orienteering problem, each location also has a random processing time which is realized only when that location is visited. The objective here is to find a non-anticipatory policy to visit locations that maximizes the expected reward subject to the total distance plus processing time being at most B. Due to its adaptive nature, even storing a feasible policy might require exponential space. We focus on a simpler class of “non-adaptive” policies that are just specified by a permutation of the locations, and obtain positive and negative results on how well such policies approximate the optimal adaptive policy. This talk is based on joint works with Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy and R.Ravi. BIO:Viswanath Nagarajan is an Assistant Professor in the Department of Industrial and Operations Engineering, University of Michigan. From 2009-14 he was a Research Staff Member at the IBM T.J. Watson Research Center. He has a Ph.D. in Algorithms, Combinatorics and Optimization from Carnegie Mellon University (2009) and a B.Tech. in Computer Science from IIT Bombay (2003). Dr. Nagarajan's research interests are in combinatorial optimization and approximation algorithms, especially as applied to routing, location and scheduling. He received the Gerald L. Thompson dissertation award at CMU (2009), a best paper award at the European Symposium on Algorithms (2010), and two Outstanding Technical Achievement awards at IBM (2012 and 2014).