  We give improved approximations for two metric Traveling Salesman Problem
(TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a
subset of nodes $o_1, \ldots, o_k$. The TSP solution must have that $o_{i+1}$
is visited at some point after $o_i$ for each $1 \leq i < k$. This is the
special case of Precedence-Constrained TSP ($PTSP$) in which the precedence
constraints are given by a single chain on a subset of nodes. In $k$-Person TSP
Path (k-TSPP), we are given pairs of nodes $(s_1,t_1), \ldots, (s_k,t_k)$. The
goal is to find an $s_i$-$t_i$ path with minimum total cost such that every
node is visited by at least one path.
  We obtain a $3/2 + e^{-1} < 1.878$ approximation for OTSP, the first
improvement over a trivial $\alpha+1$ approximation where $\alpha$ is the
current best TSP approximation. We also obtain a $1 + 2 \cdot e^{-1/2} < 2.214$
approximation for k-TSPP, the first improvement over a trivial
$3$-approximation.
  These algorithms both use an adaptation of the Bridge Lemma that was
initially used to obtain improved Steiner Tree approximations [Byrka et al.,
2013]. Roughly speaking, our variant states that the cost of a cheapest forest
rooted at a given set of terminal nodes will decrease by a substantial amount
if we randomly sample a set of non-terminal nodes to also become terminals such
provided each non-terminal has a constant probability of being sampled. We
believe this view of the Bridge Lemma will find further use for improved
vehicle routing approximations beyond this paper.
