Approximation algorithms for some Minimum Postmen Cover Problems.

In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G = (V , E) by a minimum size set of closed walks of bounded length λ. The MCPCP is a special case of the MRPCP with R = E. We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively. [ABSTRACT FROM AUTHOR]