文献类型：期刊文献

英文题名：Approximation Algorithms fortheMin-Max Mixed Rural Postmen Cover Problem andIts Variants

作者：Huang, Liting[1]; Yu, Wei[1]; Liu, Zhaohui[1]

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2022

卷号：13595 LNCS

起止页码：36

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20230713596412)

基金：Acknowledgements. 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.

语种：英文

外文关键词：Cranes - Directed graphs - Undirected graphs

摘要：In this paper, we introduce the Min-Max Mixed Rural Postmen Cover Problem (MRPCP), which is an extension of the Mixed Rural Postman Problem to the situation where several postmen (or vehicles) are available. Given a mixed graph G= (V, E, A) with vertex set V, (undirected) edge set E, (directed) arc set A. Each edge and arc is associated with a nonnegative weight (or length). The MRPCP is to find at most k closed walks to cover a set F? E of required edges and a set H? A of required arcs. The goal is to minimize the maximum weight of the closed walks. We also study two variants of the MRPCP. The first one is the Min-Max Mixed Rural Postmen Walk Cover Problem (MRPWCP) in which the closed walks are replaced by (open) walks. The second one is called the Min-Max Mixed Chinese Postmen Cover Problem (MCPCP), which is a special case of the MRPCP where F= E and H= A. If the input graph satisfies the weakly symmetric condition, i.e. for every arc there is a parallel edge of no greater weight, we propose an algorithm for the MRPCP, whose approximation ratio lies between 335 and 274 depending on the ratio of the weight of H to that of F. When F= ? and H= A, it is a 335 -approximation algorithm for the Min-Max Stacker Crane Cover Problem (SCCP). In addition, we devise the first constant-factor approximation algorithms for the MRPWCP and the MCPCP with ratios 5 and 4, respectively, when the input graphs satisfy the weakly symmetric condition. ? 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.