4 papers
Approximating Prize-Collecting TSP below 1.556
Hong Li
The prize-collecting traveling salesperson problem is a variant of the metric traveling salesperson problem in which vertices may be left unvisited by paying their associated penal…
Approximating the Rural Postman Problem below 3/2
Hong Li, Jianping Li, Wei Li +2
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…
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…
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…