Approximation algorithms for the prize-collecting rural postman problem

Abstract

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 whose edges have nonnegative lengths and nonnegative profits, together with a specified root vertex. The goal is to find a closed walk that starts and ends at the root vertex and minimizes the sum of the walk 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 solution to the PCTSP instance into a solution to the PCRPP instance. We show that this approach has an inherent factor-two barrier: even if the constructed PCTSP instance is solved exactly, the resulting solution to the PCRPP instance can have objective value arbitrarily close to twice the optimum value of the PCRPP instance. Our main result is a polynomial time approximation algorithm with an approximation ratio strictly smaller than 1.6 for the PCRPP. On a public benchmark set of 118 instances, the proposed algorithm has average and maximum optimality gaps of 3.39% and 12.12%, respectively.

32 pages, 2 figures