论文标题
改进的近似保证金可奖励TSP
An improved approximation guarantee for Prize-Collecting TSP
论文作者
论文摘要
我们提出了一种新的近似算法，用于（公制）收集销售人员问题（PCTSP）。在与经典旅行销售人员问题（TSP）相反的PCTSP中，以给定顶点依赖的罚款为代价，可能不包括输入图的顶点，目的是平衡旅行的长度和通过最小化两者的总和来平衡省略的罚款。我们提出了一种算法，该算法在自然线性编程放宽方面可实现$ 1.774 $的近似保证。这大大减少了经典TSP和PCTSP的近似性之间的差距，超过了先前最著名的近似因子$ 1.915 $。作为我们改进的关键要素，我们提出了一种用于LP放松解决方案的精制分解技术，并展示如何利用该分解的组件作为我们旅行的构建块。
We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of $1.774$ with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of $1.915$. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.
