A better-than-1.6-approximation for prize-collecting TSP

• 成果类型: Article; Early Access
• 署名作者: Blauth, Jannis; Klein, Nathan; Nagele, Martin
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Boston University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02221-4
• 发表日期: 2025
• 关键词: traveling salesman; Approximation algorithms; connectivity; TREE

摘要

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+5)/2 approximate to 1.618\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1+\sqrt{5})\big /2 \approx 1.618$$\end{document}, 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.