  We design and analyse approximation algorithms for the minimum-cost connected
T-join problem: given an undirected graph G = (V;E) with nonnegative costs on
the edges, and a subset of nodes T, find (if it exists) a spanning connected
subgraph H of minimum cost such that every node in T has odd degree and every
node not in T has even degree; H may have multiple copies of any edge of G. Two
well-known special cases are the TSP (|T| = 0) and the s-t path TSP (|T| = 2).
Recently, An, Kleinberg, and Shmoys [STOC 2012] improved on the long-standing
5/3-approximation guarantee for the latter problem and presented an algorithm
based on LP rounding that achieves an approximation guarantee of (1+sqrt(5))/2
< 1.6181.
  We show that the methods of An et al. extend to the minimum-cost connected
T-join problem. They presented a new proof for a 5/3-approximation guarantee
for the s-t path TSP; their proof extends easily to the minimum-cost connected
T-join problem. Next, we improve on the approximation guarantee of 5/3 by
extending their LP-rounding algorithm to get an approximation guarantee of 13/8
= 1.625 for all |T| >= 4.
  Finally, we focus on the prize-collecting version of the problem, and present
a primal-dual algorithm that is "Lagrangian multiplier preserving" and that
achieves an approximation guarantee 3 - 2/(|T|-1) when |T| >= 4. Our
primal-dual algorithm is a generalization of the known primal-dual
2-approximation for the prize-collecting s-t path TSP. Furthermore, we show
that our analysis is tight by presenting instances with |T| >= 4 such that the
cost of the solution found by the algorithm is exactly 3 - 2/(|T|-1) times the
cost of the constructed dual solution.
