Improved approximation algorithms for some min–max postmen cover problems with applications to the min–max subtree cover

Wei Yu ()
Additional contact information
Wei Yu: East China University of Science and Technology

Mathematical Methods of Operations Research, 2023, vol. 97, issue 1, No 6, 135-157

Abstract: Abstract In this paper, we devise improved approximation algorithms for the Min–Max Rural Postmen Cover Problem (RuralPostCover) and the Min–Max Chinese Postmen Cover Problem (ChinesePostCover), which are natural extensions of the classical Rural Postman Problem and the Chinese Postman Problem where multiple postmen are available. These results are based on some key observations, a new approach to derive closed walks from (open) walks and an efficient postmen allocation procedure in the literature. As an application of the algorithm for RuralPostCover, we give the first constant-factor approximation algorithms for the Min–Max Subtree Cover Problem (SubtreeCover) and its generalization, called the Min–Max Steiner Tree Cover Problem with Vertex Weights (SteinerTreeCover), using simple approximation preserving reductions. Moreover, we devise specialized algorithms for SteinerTreeCover (SubtreeCover) with better approximation ratios.

Keywords: Approximation algorithm; Rural Postman problem; Chinese Postman problem; Rural Postmen cover; Min–max objective (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-022-00807-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:97:y:2023:i:1:d:10.1007_s00186-022-00807-8

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-022-00807-8

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().