3 papers
cs.DS2026
A Note on Approximating the Rural Postman Problem below 3/2
Hong Li
We give an approximation algorithm for the rural postman problem with approximation ratio strictly smaller than . We obtain this result by adapting to the rural postman proble…
cs.DS2026
Reducing Prize-Collecting Stroll and Related Routing Problems to Prize-Collecting TSP
Hong Li
The prize-collecting stroll is the path version of the prize-collecting TSP. Given a complete metric graph, two distinct prescribed terminal vertices , and nonnegative penalt…
cs.DS2026
Approximation algorithms for the prize-collecting rural postman problem
Hong Li, Jianping Li, Wei Li +2
In this paper, we study the prize-collecting rural postman problem (PCRPP), a variant of the rural postman problem. In an instance of the PCRPP, one is given an undirected graph wh…