Approximation algorithms for some min-max postmen cover problems
From MaRDI portal
Publication:2241210
DOI10.1007/s10479-021-03933-4zbMath1480.90216OpenAlexW3135507527MaRDI QIDQ2241210
Wei Yu, Xiaoguang Bao, Zhaohui Liu
Publication date: 8 November 2021
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-021-03933-4
approximation algorithmtraveling salesman problemrural postman problemChinese postman problempostmen cover
Minimax problems in mathematical programming (90C47) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (7)
Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover ⋮ Approximation algorithms for some min-max and minimum stacker crane cover problems ⋮ Approximation algorithms for some min-max and minimum stacker crane cover problems ⋮ Approximation algorithms for some minimum postmen cover problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of \(k\)-Chinese postman problem
- New inapproximability bounds for TSP
- Approximation hardness of min-max tree covers
- On the complexity of partitioning graphs into connected subgraphs
- Min-max cover of a graph with a small number of parts
- Constant-factor approximations for capacitated arc routing without triangle inequality
- Solvable cases of the \(k\)-person Chinese postman problem
- Better approximability results for min-max tree/cycle/path cover problems
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- The NP-Completeness of Some Edge-Partition Problems
- Approximation Algorithms for Some Postman Problems
- Matching, Euler tours and the Chinese postman
- Arc Routing Problems, Part II: The Rural Postman Problem
- An improved approximation algorithm for TSP in the half integral case
- Arc Routing
- Approximations for minimum and min-max vehicle routing problems
- Maximum matching and a polyhedron with 0,1-vertices
- Combinatorial optimization. Theory and algorithms
This page was built for publication: Approximation algorithms for some min-max postmen cover problems
