文献类型：期刊文献

英文题名：Approximation Algorithms for the Min-Max Mixed Rural Postmen Cover Problem and Its Variants

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

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

年份：2024

卷号：86

期号：4

起止页码：1135

外文期刊名：ALGORITHMICA

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

基金：The authors are very grateful to the anonymous referees for their valuable and constructive comments, which significantly improve the presentation of the paper. This research is supported by the National Natural Science Foundation of China under Grant Nos. 11671135, 11871213 and the Natural Science Foundation of Shanghai under Grant No. 19ZR1411800.

语种：英文

外文关键词：Approximation algorithm; Mixed Chinese postman problem; Mixed rural postman problem; Stacker crane problem; Postmen cover

摘要：In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min-Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V,E,A), where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F subset of E (H subset of A) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min-Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min-Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A. The Min-Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = (sic) and H = A. For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27/4-approximation algorithm. This algorithm achieves an approximation ratio of 33/5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition.