Abstract:In this paper, we study the prize-collecting rural postman problem (PCRPP), a variant of the rural postman problem. Given a PCRPP instance consisting of an undirected graph whose edges have nonnegative lengths and nonnegative profits, together with a root vertex, the goal is to find a closed walk that starts and ends at the root vertex and minimizes the sum of its length and the profits of all edges that the walk does not traverse. A natural way to design an approximation algorithm for the PCRPP is to construct a prize-collecting traveling salesman problem (PCTSP) instance from the given PCRPP instance, apply an approximation algorithm to the PCTSP instance, and then convert the resulting PCTSP solution into a PCRPP solution. We show that this approach has an inherent factor-two barrier: even if the constructed PCTSP instance is solved exactly, the resulting PCRPP solution can have objective value arbitrarily close to twice the optimum value of the original PCRPP instance. Our main result is a polynomial-time approximation algorithm with approximation ratio strictly smaller than 1.6 for the PCRPP. On a public 118-instance benchmark set, the proposed algorithm has average and maximum optimality gaps of 3.39\% and 12.12\%, respectively.
| Comments: | 33 pages, 2 figures |
| Subjects: | Data Structures and Algorithms (cs.DS) |
| MSC classes: | 68W25, 90C27, 90C35 |
| ACM classes: | F.2.2; G.2.2; G.1.6 |
| Cite as: | arXiv:2605.24944 [cs.DS] |
| (or arXiv:2605.24944v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24944 arXiv-issued DOI via DataCite (pending registration) |
From: Hong Li [view email]
[v1]
Sun, 24 May 2026 08:45:58 UTC (92 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。