Paper Info
Title
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^2k)$-approximation algorithm. We also show that the adaptivity gap of this problem is between $e$ and $O(log^2k)$.
Year
DOI
Venue
2017
10.4230/LIPIcs.FSTTCS.2017.27
FSTTCS
DocType
Volume
Citations 
Conference
abs/1610.01058
0
PageRank 
References 
Authors
0.34
7
3
Name
Order
Citations
PageRank
Alina Ene140925.47
VISWANATH NAGARAJAN264246.44
Rishi Saket318416.70