.png){kind=icon}
.png){kind=icon}
Return
Approximation algorithms for some min-max postmen cover problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-021-03933-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We investigate two min-max k-postmen cover problems. The first is the Min-Max Rural Postmen Cover Problem (RPC), in which we are given an undirected weighted graph and the objective is to find at most k closed walks, covering a required subset of edges, to minimize the weight of the maximum weight closed walk. The other is called the Min-Max Chinese Postmen Cover Problem, in which the goal is to find at most k closed walks, covering all the edges of an undirected weighted graph, to minimize the weight of the maximum weight closed walk. For both problems we propose the first constant-factor approximation algorithms with ratios 10 and 4, respectively. For the Metric RPC, a special case of the RPC with the edge weights obeying the triangle inequality, we obtain an improved 6-approximation algorithm by a matching-based approach. For the Min-Max Rural Postmen Walk Cover Problem (RPWC), a variant of the RPC with the closed walks replaced by (open) walks, we give a 5-approximation algorithm that improves on the previous 7-approximation algorithm. If k is fixed, we devise improved approximation algorithms for the Metric RPC and the RPWC with ratios 4+epsilon and 3+epsilon, respectively, where epsilon>0 is an arbitrary small constant. The latter result improves on the existing (4+epsilon)-approximation algorithm. Moreover, we develop a (3+epsilon)-approximation algorithm for a special case of the RPC with fixed k, improving on the previous (4+epsilon)-approximation algorithm.
Keywords:
Approximation algorithm
Traveling salesman problem
Rural postman problem
Chinese postman problem
Postmen cover
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W