Approximating Minimum-Cost Connected T-Joins

作者：Cheriyan Joseph^*; Friggstad Zachary; Gao Zhihan

来源：Algorithmica, 2015, 72(1): 126-147.

DOI：10.1007/s00453-013-9850-8

• Approximation algorithms
• LP rounding
• Primal-dual method
• Prize-collecting problems
• T-Joins
• Traveling Salesman Problem
• s, t-Path TSP

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 set of nodes TaS dagger V, 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=a...) and the s,t path TSP (T={s,t}). Recently, An et al. (Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 875-886, 2012) improved on the long-standing approximation guarantee for the latter problem and presented an algorithm based on LP rounding that achieves an approximation guarantee of .
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 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 by extending their LP-rounding algorithm to get an approximation guarantee of for all |T|a parts per thousand yen4.
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 of when |T|a parts per thousand yen4. 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|a parts per thousand yen4 such that the cost of the solution found by the algorithm is exactly times the cost of the constructed dual solution.

• 出版日期2015-5