Combinatorial Optimization Reading Group - David Aleman

Title: Approximation algorithm for stochastic k-TSP

Abstract: The input of the deterministic k-TSP problem consists of a metric complete graph with root p in which the nodes are assigned a fixed non-negative reward. The objective is to construct a p-rooted path of minimum length that collects total reward at least k. In this talk we will explore a stochastic variant of this problem in which the rewards assigned to the nodes are independent random variables, and the objective is to derive a policy that minimizes the expected length of a p-rooted path that collects total reward at least k. We will discuss approximation algorithms for this problem proposed in a paper by Ene, Nagarajan and Saket, and a paper by Jiang, Li, Liu and Singla.