A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree

DOI10.1016/j.dam.2003.06.001zbMath1061.90096OpenAlexW2027163500MaRDI QIDQ1827840

Hiroshi Nagamochi, Kohei Okada

Publication date: 6 August 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.06.001

zbMATH Keywords

Traveling salesman problemNP-hardApproximation algorithmVehicle routingTreeGraph partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Related Items (10)

An overview of graph covering and partitioning ⋮ On optimal coverage of a tree with multiple robots ⋮ Unnamed Item ⋮ Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover ⋮ Locating and repairing faults in a network with mobile agents ⋮ A note on the minimum bounded edge-partition of a tree ⋮ Minmax subtree cover problem on cacti ⋮ Approximation results for min-max path cover problems in vehicle routing ⋮ Minmax Tree Cover in the Euclidean Space ⋮ Approximation results for a min-max location-routing problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vehicle scheduling on a tree with release and handling times
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• The shifting algorithm technique for the partitioning of trees
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Routing and Scheduling on a Shoreline with Release Times
• Special cases of traveling salesman and repairman problems with time windows
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
• Complexity Of The Single Vehicle Scheduling Problem On Graphs
• Sales‐delivery man problems on treelike networks
• A new approximation algorithm for the capacitated vehicle routing problem on a tree

This page was built for publication: A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree