A 53-approximation algorithm for the clusterd traveling salesman tour and path problems

DOI10.1016/S0167-6377(98)00046-7MaRDI QIDQ1306365zbMATH OpenOpenAlexFDO

Authors Shoshana Anily, Julien Bramel, Alain Hertz

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

analysis of algorithmstransportationvehicle routingsuboptimal algorithmsordered cluster traveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• An approximation algorithm for the clustered path travelling salesman problem
• An improved approximation algorithm for the clustered traveling salesman problem
• scientific article; zbMATH DE number 1379308
• An approximation algorithm for the clustered path travelling salesman problem

Cites work

• scientific article; zbMATH DE number 1302021 (Why is no real title available?)
• An Approximation Algorithm for the Traveling Salesman Problem with Backhauls
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Procedures for travelling salesman problems with additional constraints
• Restricted delivery problems on a network
• Tight bounds for christofides' traveling salesman heuristic

Cited in

(18)

• On Residual Approximation in Solution Extension Problems
• Vertices removal for feasibility of clustered spanning trees
• On residual approximation in solution extension problems
• Approximation algorithms with constant ratio for general cluster routing problems
• A hybrid metaheuristic for the clustered travelling salesman problem
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Traveling salesman path problems
• Traveling salesman problem with clustering
• Approximation algorithms for not necessarily disjoint clustered TSP
• New mixed integer linear programming models and an iterated local search for the clustered traveling salesman problem with relaxed priority rule
• Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems
• An approximation algorithm for the clustered path travelling salesman problem
• An approximation algorithm for the clustered path travelling salesman problem
• Improving approximation ratios for the clustered traveling Salesman problem
• Cluster-level operations planning for the out-of-position robotic arc-welding
• Achieving feasibility for clustered traveling salesman problems using PQ‐trees
• An exact algorithm for the clustered travelling salesman problem
• GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306365)