*Result*: 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 G = (V,E), and a required subset R ⊆ E of edges, where each edge in E has a nonnegative weight, the objective is to find at most k closed walks covering all the edges in R such that the maximum weight of the closed walks is minimum.We propose a bicriteria (16 3 , 7 4)-approximation algorithm for the MMRPCP. More exactly, given any instance I of the MMRPCP consisting of a positive integer k, a graph G and a required edge set R, the algorithm can produce at most 7 4k closed walks covering all the edges in R such that the maximum weight of the closed walks is no more than 16 3 times the optimal value of I. Previously, the best-known approximation ratio for the MMRPCP is 6. Our result demonstrates that a moderate relaxation of the constraint on the number of closed walks is helpful to reduce the approximation ratio. [ABSTRACT FROM AUTHOR]*