Algorithms and Adaptivity Gaps for Stochastic $k$-TSP

Given a metric $(V,d)$ and a $textsf{root} in V$, the classic $textsf{$k$-TSP}$ problem is to find a tour originating at the $textsf{root}$ of minimum length that visits at least $k$ nodes in $V$. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochast