Approximation algorithms for general cluster routing problem

DOI10.1007/978-3-030-58150-3_38MaRDI QIDQ2019492zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 April 2021

Full work available at URL https://arxiv.org/abs/2006.12929

zbMATH Keywords

approximation algorithmrouting problemgeneral routing problem

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Approximation algorithms with constant ratio for general cluster routing problems
• scientific article; zbMATH DE number 1302021
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• An approximation algorithm for the clustered path travelling salesman problem
• Approximation algorithms for two clustered arc routing problems

Cites work

• A note on the prize collecting traveling salesman problem
• An approximation algorithm for the general routing problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Eight-fifth approximation for the path TSP
• P-Complete Approximation Problems
• Reducibility among combinatorial problems
• Restricted delivery problems on a network
• The salesman's improved paths through forests
• The traveling salesman problem and its variations
• Traveling salesman path problems

Cited in

(4)

• A LP-based approximation algorithm for generalized traveling salesperson path problem
• Approximation algorithms for two clustered arc routing problems
• Algorithms for generalized round robin routing
• Approximation algorithms with constant ratio for general cluster routing problems

This page was built for publication: Approximation algorithms for general cluster routing problem

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