An approximation algorithm for the clustered path travelling salesman problem
From MaRDI portal
Publication:6167001
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
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