Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover

摘要

In this paper, we devise improved approximation algorithms for the Min-Max Rural Postmen Cover Problem (RuralPostCover) and the Min-Max Chinese Postmen Cover Problem (ChinesePostCover), which are natural extensions of the classical Rural Postman Problem and the Chinese Postman Problem where multiple postmen are available. These results are based on some key observations, a new approach to derive closed walks from (open) walks and an efficient postmen allocation procedure in the literature. As an application of the algorithm for RuralPostCover, we give the first constant-factor approximation algorithms for the Min-Max Subtree Cover Problem (SubtreeCover) and its generalization, called the Min-Max Steiner Tree Cover Problem with Vertex Weights (SteinerTreeCover), using simple approximation preserving reductions. Moreover, we devise specialized algorithms for SteinerTreeCover (SubtreeCover) with better approximation ratios.