Approximation algorithms for some min-max postmen cover problems

doi:10.1007/s10479-021-03933-4

Return

Approximation algorithms for some min-max postmen cover problems

2021-03-06

PRE

DOI：10.1007/s10479-021-03933-4

Original

Original request for help

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.