A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems

DOI10.1016/S0167-6377(98)00046-7zbMath0956.90035OpenAlexW2162344698MaRDI QIDQ1306365

Alain Hertz, Julien Bramel, Shoshana Anily

Publication date: 1999

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(98)00046-7

zbMATH Keywords

transportationvehicle routinganalysis of algorithmssuboptimal algorithmsordered cluster traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (14)

On residual approximation in solution extension problems ⋮ Approximation Algorithms for Not Necessarily Disjoint Clustered TSP ⋮ GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem ⋮ Vertices removal for feasibility of clustered spanning trees ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ On Residual Approximation in Solution Extension Problems ⋮ Achieving feasibility for clustered traveling salesman problems using PQ‐trees ⋮ New mixed integer linear programming models and an iterated local search for the clustered traveling salesman problem with relaxed priority rule ⋮ An exact algorithm for the clustered travelling salesman problem ⋮ Traveling salesman path problems ⋮ Cluster-level operations planning for the out-of-position robotic arc-welding ⋮ Approximation algorithms with constant ratio for general cluster routing problems

Cites Work

• Unnamed Item
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Procedures for travelling salesman problems with additional constraints
• Tight bounds for christofides' traveling salesman heuristic
• Restricted delivery problems on a network
• An Approximation Algorithm for the Traveling Salesman Problem with Backhauls

This page was built for publication: A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems