Approximation algorithms with constant ratio for general cluster routing problems
From MaRDI portal
Publication:2084625
DOI10.1007/s10878-021-00772-8zbMath1504.90142OpenAlexW3173859340MaRDI QIDQ2084625
Publication date: 18 October 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-021-00772-8
traveling salesman problemcombinatorial approximation algorithmgeneral cluster routing problemgraph routing problem
Cites Work
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- A note on the prize collecting traveling salesman problem
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- An approximation algorithm for the general routing problem
- A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
- Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
- TSP heuristics: domination analysis and complexity
- Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
- The traveling salesman problem and its variations
- Approximation algorithms for general cluster routing problem
- \(\frac{13}{9}\)-approximation for graphic TSP
- Traveling salesman path problems
- Finding thet-join structure of graphs
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- On some connectivity properties of Eulerian graphs
- P-Complete Approximation Problems
- A statistical approach to the tsp
- Approximation Algorithms for Some Postman Problems
- Restricted delivery problems on a network
- Eight-Fifth Approximation for the Path TSP
- Reducibility among Combinatorial Problems
- The Salesman’s Improved Paths through Forests
- A 1.5-Approximation for Path TSP
- Approaching 3/2 for the s - t -path TSP
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This page was built for publication: Approximation algorithms with constant ratio for general cluster routing problems
