Approximating minimum-cost connected \(T\)-joins (Q2345942): Difference between revisions

The present paper analyses the minimum-cost connected \(T\)-join optimization problem: given an undirected graph \(G = (V,E)\) with nonnegative costs on the edges, and a set of nodes \(T\subseteq V\), find 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. There are known multiple approximation algorithms for two special cases: the TSP (\(T =\emptyset\)) and the \(s, t\)-path TSP (\(T = \{s, t\}\)). The most recent improvements were given by \textit{H.-C. An} et al. [in: Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY: Association for Computing Machinery (ACM). 875--886 (2012; Zbl 1286.68173)], who presented an algorithm based on LP rounding that achieves an approximation guarantee of \(1+5\sqrt2\approx 1.61803\), and by \textit{A. Sebő} [Lect. Notes Comput. Sci. 7801, 362--374 (2013; Zbl 1336.90098)], who presented an \(\frac85\) approximation algorithm. The approximation algorithm proposed in this paper is based on the methods of An et al. [loc. cit.], since their proof for a \(\frac53\) approximation guarantee for the \(s, t\)-path TSP extends easily to the minimum-cost connected \(T\)-join problem. An approximation guarantee of the improved algorithm is \(\frac{13}8 = 1.625\) for all \(|T|\geq4\). The second result pertains to the prize-collecting version of the problem: there is additional nonnegative penalty \(n(v)\) for each node \(v\in V-T\); the goal is to find \(I\subseteq V-T\) and a connected \(T\)-join \(F\) of the graph \(G-I\) such that \(\operatorname{cost}(F) + n(I)\) is minimized. The authors present a tight primal-dual algorithm that achieves an approximation guarantee of \(3 - \frac4{|T|}\) when \(|T|\geq4\).