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

DOI10.1007/s00186-022-00807-8OpenAlexW4311717631MaRDI QIDQ2699031

Wei Yu

Publication date: 26 April 2023

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00186-022-00807-8

zbMATH Keywords

approximation algorithmrural postman problemChinese postman problemmin-max objectiverural postmen cover

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• Parameterized complexity of \(k\)-Chinese postman problem
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Min-max tree covers of graphs.
• Approximation hardness of min-max tree covers
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• Constant-factor approximations for capacitated arc routing without triangle inequality
• A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree
• Solvable cases of the \(k\)-person Chinese postman problem
• Approximation algorithms for some min-max postmen cover problems
• Exact and approximation algorithms for the min-max \(k\)-traveling salesmen problem on a tree
• Solution of a Min-Max Vehicle Routing Problem
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• A fundamental problem in vehicle routing
• Algorithms and Computation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Approximations for minimum and min-max vehicle routing problems
• Combinatorial optimization. Theory and algorithms
• Approximation algorithms for some minimum postmen cover problems

This page was built for publication: Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover