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.