Approximation hardness of min-max tree covers

DOI10.1016/j.orl.2010.02.004zbMath1187.90240OpenAlexW1976697723MaRDI QIDQ974986

Zhou Xu, Qi Wen

Publication date: 8 June 2010

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2010.02.004

zbMATH Keywords

vehicle routinginapproximability boundmin-Maxtree covers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An overview of graph covering and partitioning ⋮ Approximation and polynomial algorithms for the data mule scheduling with handling time and time span constraints ⋮ Better approximability results for min-max tree/cycle/path cover problems ⋮ 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 ⋮ Unnamed Item ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ Min-max cover of a graph with a small number of parts ⋮ Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems ⋮ Vehicle routing with subtours ⋮ Approximation results for min-max path cover problems in vehicle routing ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems ⋮ Approximation results for a min-max location-routing problem

Cites Work

• Unnamed Item
• Min-max tree covers of graphs.
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• On the approximability of the traveling salesman problem
• Algorithms and Computation
• Approximations for minimum and min-max vehicle routing problems