Approximation algorithms with constant ratio for general cluster routing problems

DOI10.1007/S10878-021-00772-8MaRDI QIDQ2084625zbMATH OpenOpenAlexFDO

Authors Yanyan Li

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

zbMATH Keywords

combinatorial approximation algorithmgeneral cluster routing problemgraph routing problemtraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• scientific article; zbMATH DE number 1302021
• An improved approximation algorithm for the clustered traveling salesman problem
• An approximation algorithm for the general routing problem
• An approximation algorithm for the clustered path travelling salesman problem

Cites work

• \(\frac{13}{9}\)-approximation for graphic TSP
• A 1.5-approximation for path TSP
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• A note on the prize collecting traveling salesman problem
• A statistical approach to the tsp
• An approximation algorithm for the general routing problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Approximation algorithms for general cluster routing problem
• Approximation Algorithms for Some Postman Problems
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Eight-fifth approximation for the path TSP
• Finding thet-join structure of graphs
• Improving Christofides' algorithm for the s-t path TSP
• On some connectivity properties of Eulerian graphs
• P-Complete Approximation Problems
• Reducibility among combinatorial problems
• Removing and adding edges for the traveling salesman problem
• Restricted delivery problems on a network
• 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
• The salesman's improved paths through forests
• The traveling salesman problem and its variations
• Traveling salesman path problems
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• TSP heuristics: domination analysis and complexity

Cited in

(4)

• An approximation algorithm for the general routing problem
• Approximation algorithms for general cluster routing problem
• Approximating routing and connectivity problems with multiple distances
• Approximation algorithms for two clustered arc routing problems

This page was built for publication: Approximation algorithms with constant ratio for general cluster routing problems

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