Approximating TSP Variants 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₁, , oₖ. The TSP solution must have that o₈+₁ is visited at some point after oᵢ 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₁, t₁), , (sₖ, tₖ). The goal is to find an sᵢ-tᵢ 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 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.