\((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective

DOI10.1016/S0166-218X(97)89161-5zbMath0879.68077OpenAlexW2008992746MaRDI QIDQ1363767

Igor Averbakh, Oded Berman

Publication date: 11 August 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

traveling salesmanlocation-allocation problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (24)

An approximability result of the multi-vehicle scheduling problem on a path with release and handling times ⋮ On the uniform edge-partition of a tree ⋮ A subexponential algorithm for the coloured tree partition problem ⋮ An overview of graph covering and partitioning ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ The ANTS problem ⋮ 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. ⋮ How many oblivious robots can explore a line ⋮ Unnamed Item ⋮ Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover ⋮ Map construction of unknown graphs by multiple agents ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ Remembering without memory: tree exploration by asynchronous oblivious robots ⋮ Locating and repairing faults in a network with mobile agents ⋮ A note on the minimum bounded edge-partition of a tree ⋮ Approximation hardness of min-max tree covers ⋮ Minmax subtree cover problem on cacti ⋮ Approximation results for min-max path cover problems in vehicle routing ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Minmax Tree Cover in the Euclidean Space ⋮ Complexity of robust single facility location problems on networks with uncertain edge lengths. ⋮ Approximation results for a min-max location-routing problem ⋮ A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree

Cites Work

• Unnamed Item
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Two exact algorithms for the distance-constrained vehicle routing problem

This page was built for publication: \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective