|
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.
This is joint work with Joseph Cheriyan and Zhihan Gao.
|