Approximation Algorithms for Stochastic k-TSP

Abstract

We consider the stochastic $k$-TSP problem where rewards at vertices are random and the objective is to minimize the expected length of a tour that collects reward $k$. We present an adaptive $O(\log k)$-approximation algorithm, and a non-adaptive $O({\log }^{2}k)$-approximation algorithm. We also show that the adaptivity gap of this problem is between $e$ and $O({\log }^{2}k)$.

11 pages

References in corpus (1)

• Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits