Tutte seminar - Zachary Friggstad

Approximating Minimum Cost Connected T-Joins

Abstract:

Given a graph G and a subset of nodes T, a connected T-join is a connected spanning subgraph H such that T is exactly the set of even-degree nodes; H may have multiple copies of any edge of G. If the edges of G have weights, it is natural to consider the problem of finding the minimum weight connected T-join in G. This generalizes the notion of the classic traveling salesman problem (T = {}) and its path variant (T = {s,t}).

As with TSP paths, it is relatively easy to get a 5/3-approximation for the connected T-join problem. We generalize recent results by An, Kleinberg, and Shmoys on TSP paths and obtain an approximation algorithm for the connected T-join problem that finds a solution of cost at most 261/160 = 1.63125 times the cost of the optimum solution. We also show that this analysis can be improved when the size of T is bounded by a constant. Finally, we present a 3-approximation for a prize-collecting variant of the problem where we are allowed exclude some nodes from the connected T-join by paying some penalty.