文献类型：期刊文献

英文题名：Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover

作者：Yu, Wei[1]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China

年份：2023

卷号：97

期号：1

起止页码：135

外文期刊名：MATHEMATICAL METHODS OF OPERATIONS RESEARCH

收录：;EI(收录号：20225013227414);WOS:【SCI-EXPANDED(收录号:WOS:000894972000001)】；

基金：This research is supported by the National Natural Science Foundation of China under Grant numbers 11671135, 11871213 and the Natural Science Foundation of Shanghai under Grant Number 19ZR1411800.

语种：英文

外文关键词：Approximation algorithm; Rural Postman problem; Chinese Postman problem; Rural Postmen cover; Min-max objective

摘要：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.