Improving on Best-of-Many-Christofides for $T$-tours

The T -tour problem is a natural generalization of TSP and Path TSP. Given a graph G = ( V , E ) , edge cost c : E → R ≥ 0 , and an even cardinality set T ⊆ V , we want to compute a minimum-cost T -join connecting all vertices of G (and possibly containing parallel edges). In this paper we give an 11 7 -approximation for the T -tour problem and show that the integrality ratio of the standard LP relaxation is at most 11 7 . Despite much progress for the special case Path TSP, for general T -tours this is the first improvement on Sebő’s analysis of the Best-of-Many-Christofides algorithm (Sebő, 2013).