A Bicriteria Approximation Algorithm for the Min-Max Rural Postmen Cover Problem

We study approximation algorithms for the Min-Max Rural Postmen Cover Problem (MMRPCP). Given an undirected graph Formula: see text, and a required subset Formula: see text of edges, where each edge in Formula: see text has a nonnegative weight, the objective is to find at most Formula: see text closed walks covering all the edges in Formula: see text such that the maximum weight of the closed walks is minimum. We propose a bicriteria Formula: see text-approximation algorithm for the MMRPCP. More exactly, given any instance Formula: see text of the MMRPCP consisting of a positive integer Formula: see text, a graph Formula: see text and a required edge set Formula: see text, the algorithm can produce at most Formula: see text closed walks covering all the edges in Formula: see text such that the maximum weight of the closed walks is no more than Formula: see text times the optimal value of Formula: see text. Previously, the best-known approximation ratio for the MMRPCP is Formula: see text. Our result demonstrates that a moderate relaxation of the constraint on the number of closed walks is helpful to reduce the approximation ratio.