A better-than-1.6-approximation for prize-collecting TSP
针对奖赏收集旅行商问题，提出多项式时间近似算法，将近似比从1.774降至1.599，对路径版本也改进至1.6662。
Abstract Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural linear programming relaxation of the problem. This improves upon the previous best-known approximation ratio of 1.774. Our approach is based on a known decomposition for solutions of this linear relaxation into rooted trees. Our algorithm takes a tree from this decomposition and then performs a pruning step before doing parity correction on the remainder. Using a simple analysis, we bound the approximation guarantee of the proposed algorithm by $$(1+\sqrt{5})\big /2 \approx 1.618$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:msqrt> <mml:mn>5</mml:mn> </mml:msqrt> <mml:mo>)</mml:mo> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo>≈</mml:mo> <mml:mn>1.618</mml:mn> </mml:mrow> </mml:math> , the golden ratio. With some additional technical care we further improve the approximation guarantee to 1.599. Furthermore, we show that for the path version of Prize-Collecting TSP (known as Prize-Collecting Stroll) our approach yields an approximation guarantee of 1.6662, improving upon the previous best-known guarantee of 1.926.