文献类型：期刊文献

英文题名：Approximation algorithms for some Minimum Postmen Cover

作者：Mao, Yuying[1];Yu, Wei[1];Liu, Zhaohui[1];Xiong, Jiafeng[1]

机构：[1]East China Univ Sci & Technol, Dept Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

年份：2022

卷号：319

起止页码：382

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：;WOS:【SCI-EXPANDED(收录号:WOS:000911804600013)】；

基金：We are very grateful to the anonymous reviewers for their valuable suggestions and insightful comments that help us to improve the presentation of the paper. This research is supported by the National Natural Science Foundation of China (Nos. 11671135 and 11871213), the Natural Science Foundation of Shanghai, China (No. 19ZR1411800) and the Fundamental Research Fund for the Central Universities, China (No. 22220184028).

语种：英文

外文关键词：Approximation algorithm; Traveling salesman problem; Rural postman problem; Chinese postman problem; Postmen cover

摘要：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 lambda. 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. (c) 2022 Elsevier B.V. All rights reserved.