An approximation algorithm for the clustered path travelling salesman problem

DOI10.1007/978-3-031-16081-3_2zbMath1522.90169OpenAlexW4296167516MaRDI QIDQ6167001

Bo Hou, Jiaxuan Zhang, Suo-gang Gao, Wen Liu

Publication date: 7 July 2023

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-16081-3_2

zbMATH Keywords

clusterpathtravelling salesman problemstacker crane problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• The symmetric clustered traveling salesman problem
• Solution of large-scale symmetric travelling salesman problems
• Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Better \(s-t\)-tours by Gao trees
• The traveling salesman problem with backhauls
• Supereulerian digraphs
• Worst-case analysis of a new heuristic for the travelling salesman problem
• Graph Theory
• Improving Christofides' Algorithm for the s-t Path TSP
• The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic
• Restricted delivery problems on a network
• A 1.5-Approximation for Path TSP
• Approaching 3/2 for the s - t -path TSP
• Paths, Trees, and Flowers

This page was built for publication: An approximation algorithm for the clustered path travelling salesman problem