Approximating Traveling Salesman Problems Using a Bridge Lemma

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 , . . . , o k . The TSP solution must have that o i+1 is visited at some point after o i for each 1 ≤ 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 ), . . . , (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 α + 1 approximation where α is the current best TSP approximation. We also obtain a 1 + 2 • e -1/2 < 2.214 approximation for k-TSPP, the first improvement over a trivial 3approximation.

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.