文献类型：期刊文献

英文题名：A Bicriteria Approximation Algorithm for the Min-Max Rural Postmen Cover Problem

作者：Xiong, Jiafeng[1];Sun, Yuhui[1];Yu, Wei[1];Liu, Zhaohui[1]

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

年份：2026

外文期刊名：INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

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

基金：This research is supported by the National Natural Science Foundation of China (No. 12571337) and the Natural Science Foundation of Shanghai (No. 24ZR1416900).

语种：英文

外文关键词：Bicriteria approximation algorithm; rural postmen cover; min-max objective

摘要：We study approximation algorithms for the Min-Max Rural Postmen Cover Problem (MMRPCP). Given an undirected graph G = (V,E), and a required subset R subset of E of edges, where each edge in E has a nonnegative weight, the objective is to find at most k closed walks covering all the edges in R such that the maximum weight of the closed walks is minimum. We propose a bicriteria (16/ 3 , 7/ 4)-approximation algorithm for the MMRPCP. More exactly, given any instance I of the MMRPCP consisting of a positive integer k, a graph G and a required edge set R, the algorithm can produce at most 7/ 4k closed walks covering all the edges in R such that the maximum weight of the closed walks is no more than 16/ 3 times the optimal value of I. Previously, the best-known approximation ratio for the MMRPCP is 6. Our result demonstrates that a moderate relaxation of the constraint on the number of closed walks is helpful to reduce the approximation ratio.